Submission #683096

#	Time	Username	Problem	Language	Result	Execution time	Memory
683096		Alcabel	Segments (IZhO18_segments)	C++17	100 / 100	2969 ms	13928 KiB

segments

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5, perBlock = 448, maxBlocks = (maxn + perBlock - 1) / perBlock;
int prefL[maxBlocks + 1][maxBlocks + 1], prefR[maxBlocks + 1][maxBlocks + 1], blocks;
int l[maxn], r[maxn], len[maxn], lId[maxn], rId[maxn], lenId[maxn];
char isDel[maxn];
vector<int> toIns, toDel, byLen, byL, byR;

bool cmpLen(const int& A, const int& B) {
    return len[A] < len[B];
}

bool cmpL(const int& A, const int& B) {
    return l[A] < l[B];
}

bool cmpR(const int& A, const int& B) {
    return r[A] < r[B];
}

void rebuild() {
    static vector<int> tmp;
    tmp.resize(byLen.size() + toIns.size());
    // byLen
    sort(toIns.begin(), toIns.end(), cmpLen);
    merge(byLen.begin(), byLen.end(), toIns.begin(), toIns.end(), tmp.begin(), cmpLen);
    byLen.clear();
    for (const int& i : tmp) {
        if (!isDel[i]) {
            byLen.emplace_back(i);
        }
    }
    // byL
    sort(toIns.begin(), toIns.end(), cmpL);
    merge(byL.begin(), byL.end(), toIns.begin(), toIns.end(), tmp.begin(), cmpL);
    byL.clear();
    for (const int& i : tmp) {
        if (!isDel[i]) {
            byL.emplace_back(i);
        }
    }
    // byR
    sort(toIns.begin(), toIns.end(), cmpR);
    merge(byR.begin(), byR.end(), toIns.begin(), toIns.end(), tmp.begin(), cmpR);
    byR.clear();
    for (const int& i : tmp) {
        if (!isDel[i]) {
            byR.emplace_back(i);
        }
    }
    toIns.clear();
    toDel.clear();
    blocks = ((int)byLen.size() + perBlock - 1) / perBlock;
    for (int i = 1; i <= blocks; ++i) {
        for (int j = 1; j <= blocks; ++j) {
            prefL[i][j] = prefR[i][j] = 0;
        }
    }
    // byLen
    for (int bId = 0, i = 0; bId < blocks; ++bId) {
        for (int j = 0; j < perBlock && i < (int)byLen.size(); ++j, ++i) {
            lenId[byLen[i]] = bId;
        }
    }
    // byL
    for (int bId = 0, i = 0; bId < blocks; ++bId) {
        for (int j = 0; j < perBlock && i < (int)byL.size(); ++j, ++i) {
            lId[byL[i]] = bId;
        }
    }
    // byR
    for (int bId = 0, i = 0; bId < blocks; ++bId) {
        for (int j = 0; j < perBlock && i < (int)byR.size(); ++j, ++i) {
            rId[byR[i]] = bId;
        }
    }
    for (const int& i : byLen) {
        ++prefL[lenId[i] + 1][lId[i] + 1];
        ++prefR[lenId[i] + 1][rId[i] + 1];
    }
    for (int i = 1; i <= blocks; ++i) {
        for (int j = 1; j <= blocks; ++j) {
            prefL[i][j] += prefL[i - 1][j] + prefL[i][j - 1] - prefL[i - 1][j - 1];
            prefR[i][j] += prefR[i - 1][j] + prefR[i][j - 1] - prefR[i - 1][j - 1];
        }
    }
}

void solve() {
    int n, t, lastans = 0;
    cin >> n >> t;
    blocks = 0;
    for (int iter = 0, iterRest = 0, nxtIdx = 0; iter < n; ++iter, ++iterRest) {
        if (iterRest == perBlock) {
            rebuild();
            iterRest = 0;
        }
        int type;
        cin >> type;
        if (type == 1) {
            int a, b;
            cin >> a >> b;
            a ^= (t * lastans);
            b ^= (t * lastans);
            if (a > b) { swap(a, b); }
            l[nxtIdx] = a, r[nxtIdx] = b, len[nxtIdx] = b - a + 1;
            toIns.emplace_back(nxtIdx++);
        } else if (type == 2) {
            int i;
            cin >> i;
            --i;
            toDel.emplace_back(i);
            isDel[i] = true;
        } else {
            int a, b, k;
            cin >> a >> b >> k;
            a ^= (t * lastans);
            b ^= (t * lastans);
            if (a > b) { swap(a, b); }
            lastans = 0;
            if (b - a + 1 >= k) {
                // all that len[i] >= k
                int bLen = 0, bId = 0, ptrLen = 0, ptr = 0;
                // ptrLen -> start of the first block where all is good
                while (bLen < blocks && len[byLen[ptrLen]] < k) {
                    ++bLen;
                    ptrLen += perBlock;
                }
                int goodK = 0;
                goodK += prefL[blocks][blocks] - prefL[bLen][blocks];
                for (int i = max(0, ptrLen - perBlock); i < (int)byLen.size() && i < ptrLen; ++i) {
                    if (len[byLen[i]] >= k) {
                        ++goodK;
                    }
                }
                // L <= b - k + 1
                bId = 0, ptr = 0;
                // ptr -> start of the first block where smth is bad
                while (bId < blocks && l[byL[min(ptr + perBlock, (int)byL.size()) - 1]] <= b - k + 1) {
                    ++bId;
                    ptr += perBlock;
                }
                int goodKL = 0;
                goodKL += prefL[blocks][bId] - prefL[bLen][bId];
                for (int i = ptr; i < (int)byL.size() && i < ptr + perBlock; ++i) {
                    if (len[byL[i]] >= k && l[byL[i]] <= b - k + 1) {
                        ++goodKL;
                    }
                }
                for (int i = max(0, ptrLen - perBlock); i < (int)byLen.size() && i < ptrLen; ++i) {
                    if (len[byLen[i]] >= k && l[byLen[i]] <= b - k + 1) {
                        ++goodKL;
                        if (lId[byLen[i]] == bId) {
                            --goodKL;
                        }
                    }
                }
                // R >= a + k - 1
                bId = 0, ptr = 0;
                // ptr -> start of the first block where all is good
                while (bId < blocks && r[byR[ptr]] < a + k - 1) {
                    ++bId;
                    ptr += perBlock;
                }
                int goodKR = 0;
                goodKR += prefR[blocks][blocks] - prefR[bLen][blocks] - prefR[blocks][bId] + prefR[bLen][bId];
                for (int i = max(0, ptr - perBlock); i < (int)byR.size() && i < ptr; ++i) {
                    if (len[byR[i]] >= k && r[byR[i]] >= a + k - 1) {
                        ++goodKR;
                    }
                }
                for (int i = max(0, ptrLen - perBlock); i < (int)byLen.size() && i < ptrLen; ++i) {
                    if (len[byLen[i]] >= k && r[byLen[i]] >= a + k - 1) {
                        ++goodKR;
                        if (rId[byLen[i]] == bId - 1) {
                            --goodKR;
                        }
                    }
                }
                // cerr << "goodKL: " << goodKL << ", goodKR: " << goodKR << ", goodK: " << goodK << '\n';
                lastans = goodKL + goodKR - goodK;
                // fix with updates
                for (const int& i : toIns) {
                    if (l[i] <= b - k + 1 && r[i] >= a + k - 1 && len[i] >= k) {
                        ++lastans;
                    }
                }
                for (const int& i : toDel) {
                    if (l[i] <= b - k + 1 && r[i] >= a + k - 1 && len[i] >= k) {
                        --lastans;
                    }
                }
            }
            cout << lastans << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 25 / 25