Submission #175939

#	Time	Username	Problem	Language	Result	Execution time	Memory
175939		VEGAnn	Segments (IZhO18_segments)	C++14	100 / 100	4173 ms	12404 KiB

segments

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 200100;
const int BLOCK = 3000;
const int NB = N / BLOCK + 10;
const int PW = 20;
vector<int> bad, old, nw, lf, rt, glf, grt;
int last_ans = 0, n, l[N], r[N], tt = 0;
bool mrk[N], T;
 
bool cmp(int _x, int _y){
    return (r[_x] - l[_x]) < (r[_y] - l[_y]);
}
 
bool cmp_lf(int _x, int _y){
    return l[_x] < l[_y];
}
 
bool cmp_rt(int _x, int _y){
    return r[_x] < r[_y];
}
 
bool ok(int id, int l1, int r1, int k){
    int lef = max(l1, l[id]);
    int rgt = min(r1, r[id]);
    return bool((rgt - lef + 1) >= k);
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    cin >> n >> T;
 
    old.clear();
 
    for (int it = 0; it < n; it += BLOCK){
        int bd = min(n, it + BLOCK);
        int mem_tt = tt;
        bad.clear();
 
        for (int i = it; i < bd; i++){
            int tp; cin >> tp;
            if (tp == 1){
                cin >> l[tt] >> r[tt];
                if (T){
                    l[tt] = (l[tt] ^ last_ans);
                    r[tt] = (r[tt] ^ last_ans);
                }
                if (l[tt] > r[tt])
                    swap(l[tt], r[tt]);
                tt++;
            } else if (tp == 2){
                int id; cin >> id; id--;
                bad.PB(id);
                mrk[id] = 1;
            } else {
                int l1, r1, k;
                cin >> l1 >> r1 >> k;
                if (T){
                    l1 = (l1 ^ last_ans);
                    r1 = (r1 ^ last_ans);
                }
                if (l1 > r1)
                    swap(l1, r1);
 
                if (r1 - l1 + 1 < k){
                    last_ans = 0;
                    cout << "0\n";
                    continue;
                }
 
                int dl = 0;
                if (sz(lf)){
                    dl += lower_bound(all(grt), l1 + k - 1) - grt.begin();
                    dl += sz(glf);
                    dl -= upper_bound(all(glf), r1 - k + 1) - glf.begin();
 
                    for (int i = 0; i < sz(lf); i += BLOCK){
                        int bd = min(sz(lf), i + BLOCK);
                        if (r[nw[bd - 1]] - l[nw[bd - 1]] + 1 >= k){
                            for (int j = i; j < bd; j++){
                                int nm = nw[j];
                                if (r[nm] - l[nm] + 1 >= k) break;
                                if (r[nm] < l1 + k - 1)
                                    dl--;
                                if (l[nm] > r1 - k + 1)
                                    dl--;
                                dl++;
                            }
                        } else {
                            dl -= lower_bound(rt.begin() + i, rt.begin() + bd, l1 + k - 1) - rt.begin() - i;
                            dl -= bd;
                            dl += upper_bound(lf.begin() + i, lf.begin() + bd, r1 - k + 1) - lf.begin();
 
                            dl += bd - i;
                        }
                    }
                }
                int ans = sz(lf) - dl;
 
                for (int i = mem_tt; i < tt; i++)
                    if (ok(i, l1, r1, k))
                        ans++;
 
                for (int i : bad)
                    if (ok(i, l1, r1, k))
                        ans--;
 
                cout << ans << '\n';
                last_ans = ans;
            }
        }
 
        old = nw;
        nw.clear();
 
        for (int id : old)
            if (!mrk[id])
                nw.PB(id);
 
        for (int i = mem_tt; i < tt; i++)
            if (!mrk[i])
                nw.PB(i);
 
        sort(all(nw), cmp);
 
        lf.resize(sz(nw));
        rt.resize(sz(nw));
        glf.resize(sz(nw));
        grt.resize(sz(nw));
        for (int i = 0; i < sz(nw); i++){
            lf[i] = glf[i] = l[nw[i]];
            rt[i] = grt[i] = r[nw[i]];
        }
 
        for (int i = 0; i < sz(nw); i += BLOCK){
            int bd = min(sz(nw), i + BLOCK);
            sort(lf.begin() + i, lf.begin() + bd);
            sort(rt.begin() + i, rt.begin() + bd);
        }
 
        sort(all(glf));
        sort(all(grt));
    }
 
    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