Submission #485685

#	Time	Username	Problem	Language	Result	Execution time	Memory
485685		SirCovidThe19th	Segments (IZhO18_segments)	C++17	100 / 100	2878 ms	12420 KiB

segments

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

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pii pair<int, int>
#define f first
#define s second

const int mx = 2e5 + 5, sq = 1212, mxBL = mx / sq + 5, inf = 1e9 + 1;

int n, t, idcnt, lans; pii segs[mx]; 

bool cmp(pii a, pii b){
    return a.s > b.s or (a.s == b.s and a.f > b.f);
}
void get(int &a, int &b){
    a ^= (lans * t); b ^= (lans * t);
    if (a > b) swap(a, b);
}
struct DS{
    int bl, lowsz[mxBL]; vector<pii> L[mxBL], R[mxBL], allSeg; vector<pii> newElem;

    void rebuild(){
        sort(allSeg.begin(), allSeg.end(), [](pii a, pii b){ return a.s - a.f < b.s - b.f; });

        bl = 0; L[0].clear(); R[0].clear(); newElem.clear(); 
        if (!allSeg.empty()) lowsz[0] = allSeg[0].s - allSeg[0].f;

        for (pii X : allSeg){
            if (L[bl].size() >= sq){
                bl++; lowsz[bl] = X.s - X.f;
                L[bl].clear(), R[bl].clear();
            }
            L[bl].push_back(X); R[bl].push_back(X); 
        }
        FOR(i, 0, bl + 1){
            sort(L[i].begin(), L[i].end()); 
            sort(R[i].begin(), R[i].end(), cmp);
        }
    }
    void upd(int a, int b){
        allSeg.push_back(mp(a, b));
        newElem.push_back(mp(a, b));
        if (newElem.size() >= sq) rebuild();
    }
    int qry(int l, int r, int k){
        int i = bl, ret = 0;
        while (i and lowsz[i] >= k - 1){ 
            int sz = L[i].size();
            int badL = sz - (upper_bound(all(L[i]), mp(r - k + 1, inf)) - L[i].begin());
            int badR = sz - (upper_bound(all(R[i]), mp(-inf, l + k - 1), [](pii v, pii a){ return cmp(v, a); }) - R[i].begin());
            ret += sz - badL - badR;
            i--;
        }
        for (pii X : L[i]) if (X.s - X.f >= k - 1) ret += (X.f <= r - k + 1) and (X.s >= l + k - 1);
        for (pii X : newElem) if (X.s - X.f >= k - 1) ret += (X.f <= r - k + 1) and (X.s >= l + k - 1);
        return ret;
    }
}cur, rem;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    cin >> n >> t;
    FOR(i, 0, n){
        int type; cin >> type;
        
        if (type == 1){
            int a, b; cin >> a >> b; get(a, b);
            cur.upd(a, b); segs[++idcnt] = mp(a, b);
        }
        if (type == 2){
            int id; cin >> id;
            rem.upd(segs[id].f, segs[id].s);
        }
        if (type == 3){
            int a, b, k; cin >> a >> b >> k; get(a, b);
            lans = cur.qry(a, b, k) - rem.qry(a, b, k);
            cout<<lans<<"\n";
        }
    }
}

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