Submission #42811

#	Time	Username	Problem	Language	Result	Execution time	Memory
42811		minhtung0404	Segments (IZhO18_segments)	C++14	0 / 100	876 ms	7072 KiB

segments

//https://oj.uz/problem/view/IZhO18_segments

#include<bits/stdc++.h>
const int N = 2e5 + 5;
const int MAGIC = 1001;
using namespace std;

struct segment{
    int l, r, id;
};

vector <segment> mv;
set <int> ms;
int n, t, L[N], R[N], ans, cnt;
int l_sort[N], r_sort[N], l_nosort[N], r_nosort[N], p[N], num;
bool ck[N];

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

void get_L(int pos, int k){
    int Max = (pos / MAGIC + 1) * MAGIC;
    for (int i = pos; i < min(Max, cnt); i++) if (r_nosort[pos] < k) ans--;
    for (int i = Max; i < cnt; i += MAGIC){
        int x = i, y = min(i + MAGIC, cnt);
        int val = lower_bound(r_sort+x, r_sort+y, k) - r_sort - x;
        ans -= val;
    }
}

void get_R(int pos, int k){
    int Max = (pos / MAGIC + 1) * MAGIC;
    for (int i = pos; i < min(Max, cnt); i++) if (l_nosort[pos] > k) ans--;
    for (int i = Max; i < cnt; i += MAGIC){
        int x = i, y = min(i + MAGIC, cnt);
        int val = y - (upper_bound(l_sort+x, l_sort+y, k) - l_sort);
        ans -= val;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> t;
    for (int i = 1; i <= n; i++) ms.insert(i);
    while (n--){
        if (mv.size() == MAGIC){
            cnt = 0; mv.clear();
            for (int i = 1; i < N; i++) if (ck[i]) p[cnt++] = i;
            sort(p, p+cnt, [](int x, int y){return (R[x] - L[x]) < (R[y] - L[y]);});
            for (int i = 0; i < cnt; i++) l_sort[i] = l_nosort[i] = L[p[i]];
            for (int i = 0; i < cnt; i++) r_sort[i] = r_nosort[i] = R[p[i]];
            for (int i = 0; i < cnt; i += MAGIC){
                int x = i, y = min(i + MAGIC, cnt);
                sort(l_sort+x, l_sort+y);
                sort(r_sort+x, r_sort+y);
            }
        }
        int type;
        cin >> type;
        if (type == 1){
            num++;
            int l, r, id; cin >> l >> r;
            l ^= (t * ans); r ^= (t * ans); if (r < l) swap(l, r);
            id = *(ms.begin()); ms.erase(ms.begin()); ck[id] = true;
            L[id] = l; R[id] = r;
            mv.push_back({l, r, 1});
        }
        if (type == 2){
            num--;
            int id ;cin >> id;
            ck[id] = false;
            ms.insert(id);
            mv.push_back({L[id], R[id], -1});
        }
        if (type == 3){
            int l, r, k; cin >> l >> r >> k;
            l ^= (t * ans); r ^= (t * ans); if (r < l) swap(l, r);
            if (r - l + 1 < k){
                ans = 0; cout << ans << "\n";
                continue;
            }
            ans = num;
            if (cnt > 0){
                int pos = bsearch(0, cnt-1, k);
                ans -= pos;
                get_L(pos, l + k - 1);
                get_R(pos, r - k + 1);
            }
            for (int i = 0; i < mv.size(); i++){
                int x = max(mv[i].l, l), y = min(mv[i].r, r);
                if (y - x + 1 < k) ans -= mv[i].id;
            }
            cout << ans << "\n";
        }
    }
}
/*
*/

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:96:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < mv.size(); i++){
                               ^

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