/*
There is a book with N pages (indexed from 1 to N). Each page has a certain number of words.
Now play a game with a player machine. Every time you send a message to it, the message contains
the information  "the sum of words in pages from i to j (1 <= i <= j <= N) is odd or even".
The player can save this information and check whether the coming message has conflict with
the information from ALL the previous messages.  If so, return false and the game ends.
If there is no conflict, save this information and return true.

Example:
  Game one:
     [3, 5, odd] -> true
     [6, 8, even] -> true
     [3, 8, even] -> false
  Game Two:
     [2, 10, odd] -> true
     [8, 14, even] -> true
     [2, 14, even] -> true
     [8, 10, even] -> false
*/
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

enum EvenOdd {Even, Odd};

class PagesEvenOdd {
    public:
        int open;
        int close;
        EvenOdd evenOdd;
        PagesEvenOdd (int o, int c, EvenOdd evenOdd) {
            open = o;
            close = c;
            this->evenOdd = evenOdd;
        }

        void print() const {
            cout << open << " " << close << " : " << (evenOdd == Odd ? "Odd" : "Even") << endl;
        }
};

size_t hashIntervalFunc(const pair<int,int> &interval) {
    int a = 1 + interval.second;
    int b = interval.first;
    // a > b
    return hash<int>()(a*a + b);
}

struct hashInterval {
    size_t operator()(const pair<int,int> &interval) const {
        return hashIntervalFunc(interval);
    }
};

bool isConsistentRec(
    const PagesEvenOdd &p,
    unordered_map<int, vector<pair<int,int>> > &openTimeIntervals,
    unordered_map<int, vector<pair<int,int>> > &closeTimeIntervals,
    unordered_map<pair<int,int>, EvenOdd, hashInterval> &intervalIsEvenOdd ) {
    //unordered_map<pair<int,int>, EvenOdd, decltype(hashIntervalFunc)*> &intervalIsEvenOdd ) {
    pair<int,int> interval(p.open, p.close);

    if(intervalIsEvenOdd.find(interval)!=intervalIsEvenOdd.end()) {
        if(intervalIsEvenOdd[interval]==p.evenOdd)
            return true;
        cout << "Inconsistency=> ";
        p.print();
        return false;
    }

    p.print();
    openTimeIntervals[p.open].push_back(interval);
    closeTimeIntervals[p.close].push_back(interval);
    intervalIsEvenOdd[interval] = p.evenOdd;

    if(openTimeIntervals[p.open].size()>1) {
        for(auto interval : openTimeIntervals[p.open]) {
            if(interval.second != p.close) {
                int openNext = 1 + min(interval.second, p.close);
                int closeNext = max(interval.second, p.close);
                EvenOdd isOddNext = (p.evenOdd == intervalIsEvenOdd[interval]) ? Even : Odd;
                PagesEvenOdd pNext{openNext, closeNext, isOddNext};
                if(!isConsistentRec(pNext, openTimeIntervals, closeTimeIntervals, intervalIsEvenOdd))
                    return false;
            }
        }
    }
    if(closeTimeIntervals[p.close].size()>1) {
        for(auto interval : closeTimeIntervals[p.close]) {
            if(interval.first != p.open) {
                int openNext = min(interval.first, p.open);
                int closeNext = max(interval.first, p.open)-1;
                EvenOdd isOddNext = (p.evenOdd == intervalIsEvenOdd[interval]) ? Even : Odd;
                PagesEvenOdd pNext{openNext, closeNext, isOddNext};
                if(!isConsistentRec(pNext, openTimeIntervals, closeTimeIntervals, intervalIsEvenOdd))
                    return false;
            }
        }
    }
    return true;
}

bool isConsistent(vector<PagesEvenOdd> &input) {
    if(input.size() <=1)
        return true;
    unordered_map<int, vector<pair<int,int>> > openTimeIntervals;
    unordered_map<int, vector<pair<int,int>> > closeTimeIntervals;
    unordered_map<pair<int,int>, EvenOdd, hashInterval> intervalIsEvenOdd;
    //unordered_map<pair<int,int>, EvenOdd, decltype(hashIntervalFunc)*> intervalIsEvenOdd;
    for(int i=0; i<input.size(); i++) {
        if(!isConsistentRec(input[i], openTimeIntervals, closeTimeIntervals, intervalIsEvenOdd))
            return false;
    }
    return true;
}

int main() {
    vector<PagesEvenOdd> input1 = {
        {3, 5, Odd},
        {6, 8, Even},
        {3, 8, Even},
        //{7, 8, Even},
    };
    if(isConsistent(input1))
        cout << "Consistent" << endl;
    else
        cout << "Inconsistent" << endl;

    cout << endl;
    vector<PagesEvenOdd> input2 = {
        {2, 10, Odd},
        {8, 14, Even},
        {2, 14, Even},
        {8, 10, Even},
        //{9, 10, Even},
    };
    if(isConsistent(input2))
        cout << "Consistent" << endl;
    else
        cout << "Inconsistent" << endl;
    return 0;
}