Submission #93892

#	Time	Username	Problem	Language	Result	Execution time	Memory
93892		dalgerok	Segments (IZhO18_segments)	C++14	75 / 100	5004 ms	8064 KiB

segments

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



const int N = 2e5 + 5, S = 500, M = N / S + 5;



int n, t, ans;
int sz, alive, L[N], R[N];
pair < int, int > a[N];
int add[S], sz_add, del[S], sz_del;
bool killed[N];
int sz_l[S], sz_r[S];
int b_l[S][S], b_r[S][S];
int m;

inline void rebuild(){
    m = 0;
    for(int i = 1; i <= sz; i++){
        if(killed[i] == false){
            a[m++] = make_pair(R[i] - L[i] + 1, i);
        }
    }
    sort(a, a + m);
    sz_add = sz_del = 0;
    for(int i = 0; i <= m / S; i++){
        sz_l[i] = sz_r[i] = 0;
    }
    for(int i = 0; i < m; i++){
        b_l[i / S][sz_l[i / S]++] = L[a[i].second];
        b_r[i / S][sz_r[i / S]++] = R[a[i].second];
    }
    for(int i = 0; i <= m / S; i++){
        sort(b_l[i], b_l[i] + sz_l[i]);
        sort(b_r[i], b_r[i] + sz_r[i]);
    }
}

inline int intersect(int l1, int r1, int l2, int r2){
    return max(0, min(r1, r2) - max(l1, l2) + 1);
}


/// number of L > x from l to r
inline int calcL(int l, int r, int x){
    int res = 0;
    int bl = l / S, br = r / S;
    if(bl == br){
        for(int i = l; i <= r; i++){
            res += (L[a[i].second] > x);
        }
        return res;
    }
    for(int i = bl + 1; i <= br - 1; i++){
        int j = lower_bound(b_l[i], b_l[i] + sz_l[i], x + 1) - b_l[i];
        res += S - j;
    }
    for(int i = l; i < (bl + 1) * S; i++){
        res += (L[a[i].second] > x);
    }
    for(int i = br * S; i <= r; i++){
        res += (L[a[i].second] > x);
    }
    return res;
}
/// number of R < x from l to r
inline int calcR(int l, int r, int x){
    int res = 0;
    int bl = l / S, br = r / S;
    if(bl == br){
        for(int i = l; i <= r; i++){
            res += (R[a[i].second] < x);
        }
        return res;
    }
    for(int i = bl + 1; i <= br - 1; i++){
        int j = lower_bound(b_r[i], b_r[i] + sz_r[i], x) - b_r[i];
        res += j;
    }
    for(int i = l; i < (bl + 1) * S; i++){
        res += (R[a[i].second] < x);
    }
    for(int i = br * S; i <= r; i++){
        res += (R[a[i].second] < x);
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> t;
    for(int i = 1; i <= n; i++){
        if(i % S == 0){
            rebuild();
        }
        int type;
        cin >> type;
        if(type == 1){
            int l, r;
            cin >> l >> r;
            l ^= (1LL * t * ans);
            r ^= (1LL * t * ans);
            if(l > r){
                swap(l, r);
            }
            sz += 1;
            L[sz] = l;
            R[sz] = r;
            add[sz_add++] = sz;
            alive += 1;
        }
        else if(type == 2){
            int x;
            cin >> x;
            del[sz_del++] = x;
            killed[x] = true;
            alive -= 1;
        }
        else{
            int l, r, k;
            cin >> l >> r >> k;
            l ^= (1LL * t * ans);
            r ^= (1LL * t * ans);
            if(l > r){
                swap(l, r);
            }
            if(r - l + 1 < k){
                ans = 0;
                cout << "0\n";
                continue;
            }
            int res = 0;
            for(int j = 0; j < sz_add; j++){
                res += (intersect(l, r, L[add[j]], R[add[j]]) < k);
            }
            for(int j = 0; j < sz_del; j++){
                res -= (intersect(l, r, L[del[j]], R[del[j]]) < k);
            }
            int pos = lower_bound(a, a + m, make_pair(k, 0)) - a;
            res += pos;
            res += calcL(pos, m - 1, r - k + 1);
            res += calcR(pos, m - 1, l + k - 1);
            ans = alive - res;
            cout << ans << "\n";
        }
    }
}

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