Submission #485671

#	Time	Username	Problem	Language	Result	Execution time	Memory
485671		SirCovidThe19th	Segments (IZhO18_segments)	C++17	7 / 100	5070 ms	11204 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 = 1, mxBL = mx / sq + 5, inf = 1e9 + 1;

int n, t, idcnt, lans, bl; pii segs[mx]; vector<pii> L[mxBL], R[mxBL];

bool cmp(pii a, pii b){
    return a.s > b.s or (a.s == b.s and a.f > b.f);
}
void rebuild(){
    int tot = 0; map<int, vector<pii>> allSeg;

    FOR(i, 0, bl + 1) for (pii X : L[i]) allSeg[X.s - X.f].push_back({X.f, X.s}), tot++;
    
    bl = 0; L[0].clear(); R[0].clear(); 
    for (auto V : allSeg) for (pii X : V.s){
        if (L[bl].size() >= sq) bl++, 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(pii X, bool ins){
    int i = bl; 
    while (i and L[i][0].s - L[i][0].f > X.s - X.f) i--;

    auto lpos = lower_bound(all(L[i]), X);
    auto rpos = lower_bound(all(R[i]), X, [](pii a, pii v){ return cmp(a, v); });

    if (ins){
        segs[++idcnt] = X;
        L[i].insert(lpos, X), R[i].insert(rpos, X);
    }
    else L[i].erase(lpos), R[i].erase(rpos);
}
int qry(int l, int r, int k){
    int i = bl, ret = 0;
    while (i and L[i][0].s - L[i][0].f >= 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);
    return ret;
}

int main(){
    cin >> n >> t;
    FOR(i, 0, n){
        if (!(i % sq)) rebuild(); 
        int type; cin >> type;

        if (type == 1){
            int a, b; cin >> a >> b;
            a ^= (t * lans); b ^= (t * lans);
            if (a > b) swap(a, b);
            upd(mp(a, b), 1);
        }
        if (type == 2){
            int id; cin >> id;
            upd(segs[id], 0);
        }
        if (type == 3){
            int a, b, k; cin >> a >> b >> k;
            a ^= (t * lans); b ^= (t * lans);
            if (a > b) swap(a, b);
            cout<<(lans = qry(a, b, k))<<endl;
        }
    }
}

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