IOI '08 P3 - Fish

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int m;
inline int add(int x, int y) {
    x += y;
    if (x >= m) return x-m;
    return x;
}
inline int mult(int x, int y) {return (long long)x*y%m;}

// Segment Tree on Product
vector<short> product; vector<int> leftI, rightI;
inline short getVal(int node) {
    return node >= 0 ? product[node] : 1;
}
inline void createNode() {
    product.push_back(1), leftI.push_back(-1), rightI.push_back(-1);
}
void update(int node, int first, int last, int index, short value) {
    if (first+1 == last) {
        product[node] = value;
        return;
    }
    int mid = (first + last) / 2;
    if (index < mid) {
        if (leftI[node] < 0) leftI[node] = product.size(), createNode();
        update(leftI[node], first, mid, index, value);
    } else {
        if (rightI[node] < 0) rightI[node] = product.size(), createNode();
        update(rightI[node], mid, last, index, value);
    }
    product[node] = mult(getVal(leftI[node]), getVal(rightI[node]));
}
short getProduct(int node, int first, int last, int qFirst, int qLast) {
    if (node < 0 || last <= qFirst || qLast <= first) return 1;
    if (qFirst <= first && last <= qLast) return product[node];
    int mid = (first + last) / 2;
    short l = getProduct(leftI[node], first, mid, qFirst, qLast);
    short r = getProduct(rightI[node], mid, last, qFirst, qLast);
    return mult(l, r);
}

int main() {
    int n, k; cin >> n >> k >> m;
    vector<pair<int, int>> fish(n);
    for (auto &[l, g] : fish) cin >> l >> g;
    sort(fish.begin(), fish.end());

    vector<pair<int, int>> lastOfType(k);
    vector<vector<int>> nextOfType(1+k);
    for (int i = 0; i < k; ++i) lastOfType[i].second = i+1;
    for (int i = 0; i < n; ++i) lastOfType[fish[i].second-1].first = i;
    for (int i = n-1; i >= 0; --i) nextOfType[fish[i].second].push_back(i);
    sort(lastOfType.begin(), lastOfType.end());
    for (vector<int> &v : nextOfType) {
        v.shrink_to_fit();
        vector<int> temp{v.begin(), v.end()};
        swap(temp, v);
    }

    vector<int> typeIDsorted(1+k);
    for (int i = 0; i < k; ++i) typeIDsorted[lastOfType[i].second] = i;

    vector<int> eatEnd(n); // exclusive
    eatEnd[0] = 0;
    for (int i = 1; i < n; ++i) {
        eatEnd[i] = eatEnd[i-1];
        while (eatEnd[i] < n && 2*fish[eatEnd[i]].first <= fish[i].first) ++eatEnd[i];
    }

    // Go through all last of types
    vector<int> cntSoFar(1+k);
    int root = 0; // segment tree of range products over cntSoFar+1
    createNode();
    int curEatEnd = 0; // exclusive
    int combinations = 0;
    for (int id = 0; id < k; ++id) {
        auto [pos, type] = lastOfType[id];
        while (curEatEnd < eatEnd[pos]) {
            int g = fish[curEatEnd].second;
            ++cntSoFar[g];
            update(root, 0, k, typeIDsorted[g], (cntSoFar[g]+1)%m);
            nextOfType[g].pop_back();
            ++curEatEnd;
        }

        // find first in eatEnd that can eat nextOfType[type]
        int nxt = (nextOfType[type].empty() ? n : nextOfType[type].back());
        int left = id, right = k;
        while (left+1 < right) {
            int mid = (left + right) / 2;
            if (eatEnd[lastOfType[mid].first] > nxt) right = mid;
            else left = mid;
        }
        int firstCanEat = right;

        // add combinations of gems that will not be counted by future fish
        int beforeType = getProduct(root, 0, k, 0, typeIDsorted[type]); // excluding type
        //  all of type, none of firstCanEat onwards (in order of eatEnd)
        int x = mult(beforeType, getProduct(root, 0, k, typeIDsorted[type]+1, firstCanEat));
        //  not all of type, none of later types (in order of eatEnd)
        int y = mult(beforeType, cntSoFar[type]); // without the +1 (range 1 to cntSoFar, no 0, no cntSoFar+1)

        combinations = add(combinations, add(x, y));
    }
    cout << combinations << endl;
    return 0;
}