TOI10: Treasure Chest

#include <bits/stdc++.h>
using namespace std;

enum cmd {
    ADD = 0, DEL = 1
};

struct event {
    int idx, mul;
    cmd add;
    event(){}
    event(int i, int m, cmd a){
        idx = i;
        mul = m;
        add = a;
    }
    bool operator < (const event &rhs) const {
        if(idx != rhs.idx){
            return idx < rhs.idx;
        } else if(add != rhs.add){
            return add > rhs.add;
        } else {
            return mul < rhs.mul;
        }
    }
};

typedef long long lli;
typedef pair<int, int> pii;

int curr[4];
vector<int> prime = {2, 3, 5, 7};
vector<pii> factor[11];
vector<event> ev;

int primeIdx(int x){
    return lower_bound(prime.begin(), prime.end(), x) - prime.begin();
}

int main(){

    factor[2] = {pii(2, 1)};
    factor[3] = {pii(3, 1)};
    factor[4] = {pii(2, 2)};
    factor[5] = {pii(5, 1)};
    factor[6] = {pii(2, 1), pii(3, 1)};
    factor[7] = {pii(7, 1)};
    factor[8] = {pii(2, 3)};
    factor[9] = {pii(3, 2)};
    factor[10] = {pii(2, 1), pii(5, 1)};

    int nArr, Q;
    scanf("%d%d", &Q, &nArr);
    for(int q = 1; q <= Q; ++q){
        int mul, st, ed;
        scanf("%d%d%d", &mul, &st, &ed);
        ev.emplace_back(st, mul, ADD);
        ev.emplace_back(ed + 1, mul, DEL);
    }
    ev.emplace_back(nArr, 1, ADD);
    sort(ev.begin(), ev.end());

    lli mx = 0;
    int mxCnt = 0;
    int currIdx = 0;
    for(event e : ev){
        int idx = e.idx;
        int mul = e.mul;
        cmd add = e.add;
        if(idx != currIdx){
            lli nFactor = 1;
            for(int cnt : curr){
                nFactor *= (cnt + 1);
            }
            if(nFactor > mx){
                mx = nFactor;
                mxCnt = idx - currIdx;
            } else if(nFactor == mx){
                mxCnt += idx - currIdx;
            }
            currIdx = idx;
        }
        if(add == ADD){
            for(pii f : factor[mul]){
                int x = f.first;
                int cnt = f.second;
                curr[primeIdx(x)] += cnt;
            }
        } else if(add == DEL){
            for(pii f : factor[mul]){
                int x = f.first;
                int cnt = f.second;
                curr[primeIdx(x)] -= cnt;
            }
        }
    }
    cout << mx << ' ' << mxCnt;

    return 0;
}