Submission #54424

#	Time	Username	Problem	Language	Result	Execution time	Memory
54424		egorlifar	Segments (IZhO18_segments)	C++14	100 / 100	4317 ms	6268 KiB

segments

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <bits/stdc++.h>
    
     
using namespace std;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define pb push_back
#define x first
#define y second
const string FILENAME = "input";
const int MAXN = 200001;
const int MAGIC = 1500;

//12:00
//17:00
int n, t;
int id = 0;
bool alive[MAXN];
int L[MAXN + MAXN];
int ids[MAXN];
int li[MAXN], ri[MAXN];
int lsz[MAXN], rsz[MAXN];
int cntin;


bool comp(const int &a, const int &b) {
    return L[a + MAXN] - L[a] + 1 < L[b + MAXN] - L[b] + 1;
}


int cntsmall(int l, int r, int k) {
    while (l != r){
        int mid = (l + r) >> 1;
        if (rsz[mid] - lsz[mid] + 1 >= k) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (rsz[l] - lsz[l] + 1 < k) {
        return l + 1;
    }
    return l;
}
 

int getl(int pos, int k) {
    int res = 0;
    int border = (pos / MAGIC + 1) * MAGIC;
    for (int i = pos; i < min(border, cntin); i++) {
        if (rsz[i] < k) {
            res--;
        }
    }
    for (int i = border; i < cntin; i += MAGIC){
        int lb = i, rb = min(i + MAGIC, cntin);
        int val = lower_bound(ri + lb, ri + rb, k) - ri - lb;
        res -= val;
    }
    return res;
}

 
int getr(int pos, int k) {
    int res = 0;
    int border = (pos / MAGIC + 1) * MAGIC;
    for (int i = pos; i < min(border, cntin); i++) {
        if (lsz[i] > k) {
            res--;
        }
    }
    for (int i = border; i < cntin; i += MAGIC) {
        int lb  = i, rb = min(i + MAGIC, cntin);
        int val = rb - (upper_bound(li + lb, li + rb, k) - li);
        res -= val;
    }
    return res;
}


int st[1505];
bool st1[1505];
int uks;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
    cin >> n >> t;
    int cnt = 0;
    int pans = 0;
    for (int it = 0; it < n; it++) {
        if (uks >= MAGIC) {
            cntin = 0;
            uks = 0;
            for (int i = 1; i <= id; i++) {
                if (alive[i]) {
                    ids[cntin] = i;
                    cntin++;
                }
            }
            sort(ids, ids + cntin, comp);
            for (int i = 0; i < cntin; i++) {
                li[i] = lsz[i] = L[ids[i]];
            }
            for (int i = 0; i < cntin; i++) {
                ri[i] = rsz[i] = L[ids[i] + MAXN];
            }
            for (int i = 0; i < cntin; i += MAGIC){
                int lb = i, rb = min(i + MAGIC, cntin);
                sort(li + lb, li + rb);
                sort(ri + lb, ri + rb);
            }
        }
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            l ^= pans * t;
            r ^= pans * t;
            if (l > r) {
                swap(l, r);
            }
            id++;
            cnt++;
            alive[id] = true;
            L[id] = l;
            L[id + MAXN] = r;
            st[uks] = id;
            st1[uks] = 1;
            uks++;
        } else if (type == 2) {
            int id1;
            cin >> id1;
            cnt--;
            alive[id1] = false;
            st[uks] = id1;
            st1[uks] = 0;
            uks++;
        } else if (type == 3) {
            int l, r, k;
            cin >> l >> r >> k;
            l ^= pans * t;
            r ^= pans * t;
            if (l > r) {
                swap(l, r);
            }
            if (r - l + 1 < k) {
                cout << 0 << '\n';
                pans = 0;
                continue;
            }
            int ans = cnt;
            if (cntin) {
                int pos = cntsmall(0, cntin - 1, k);
                ans -= pos;
                ans += getl(pos, l + k - 1);
                ans += getr(pos, r - k + 1);
            }
            for (int j = 0; j < uks; j++) {
                int tl = max(L[st[j]], l);
                int tr = min(L[st[j] + MAXN], r);
                if (tr - tl + 1 < k) {
                    if (st1[j]) {
                        ans--;
                    } else {
                        ans++;
                    }
                }
            }
            cout << ans << '\n';
            pans = ans;
        }
    }
}       

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