Submission #1185947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185947		juliany2	Segments (IZhO18_segments)	C++20	100 / 100	2282 ms	15988 KiB

segments

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 7, B = 1900;
int q, t;
int sz;
int l[N], r[N];
bool on[N];

struct ds {
    int n;
    array<int, 2> a[N];
    vector<int> g[N];

    void reset() {
        for (int i = 0; i < n; i += B) {
            g[i / B].clear();
        }
        n = 0;
    }

    void add(int x, int y) {
        a[n] = {x, y};
        n++;
    }

    void build() {
        sort(a, a + n);

        for (int i = 0; i < n; i++) {
            g[i / B].push_back(a[i][1]);
        }

        for (int i = 0; i < n; i += B) {
            sort(all(g[i / B]));
        }
    }

    int query(int x, int l, int r) {
        int res = 0;
        for (int i = 0; i < n && a[i][0] <= x; ) {
            if (i % B == 0 && i + B - 1 < n && a[i + B - 1][0] <= x) {
                res += upper_bound(all(g[i / B]), r) - lower_bound(all(g[i / B]), l);
                i += B;
            } else {
                if (a[i][1] >= l && a[i][1] <= r)
                    res++;
                i++;
            }
        }
        return res;
    }
} ds1, ds2;

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> q >> t;

    vector<int> ops;
    int lastans = 0;

    while (q--) {
        int o;
        cin >> o;

        if (o == 1) {
            int a, b;
            cin >> a >> b;
            a ^= t * lastans;
            b ^= t * lastans;

            if (a > b)
                swap(a, b);

            sz++;
            on[sz] = 1;
            l[sz] = a, r[sz] = b;
            ops.push_back(sz);
        } else if (o == 2) {
            int id;
            cin >> id;
            on[id] = 0;
            ops.push_back(-id);
        } else {
            int a, b, k;
            cin >> a >> b >> k;
            a ^= t * lastans;
            b ^= t * lastans;

            if (a > b)
                swap(a, b);

            int ans = 0;

            if (b - a + 1 >= k) {
                ans += ds1.query(a - 1, a + k - 1, INT_MAX);
                ans += ds2.query(-k, a, b - k + 1);
            }

            for (int i : ops) {
                if (i > 0)
                    ans += min(r[i], b) - max(l[i], a) + 1 >= k;
                else
                    ans -= min(r[-i], b) - max(l[-i], a) + 1 >= k;
            }

            lastans = ans;
            cout << ans << '\n';
        }

        if (ops.size() == B) {
            ops.clear();

            ds1.reset();
            ds2.reset();

            for (int i = 1; i <= sz; i++) {
                if (on[i]) {
                    ds1.add(l[i], r[i]);
                    ds2.add(-(r[i] - l[i] + 1), l[i]);
                }
            }

            ds1.build();
            ds2.build();
        }
    }

    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