Submission #1083603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083603		LOLOLO	Segments (IZhO18_segments)	C++17	100 / 100	2326 ms	9604 KiB

segments

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

#define           s     second
#define           f     first
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 10;
const int block = 1e3;

int l[N], r[N];

struct {
    vector <pair <int, int>> st, cur;
    vector <int> ls[N / block + 10], rs[N / block + 10];

    void add(int l, int r) {
        cur.pb({l, r});
        if (sz(cur) >= block) {
            for (auto x : cur) {
                st.pb(x);
            }

            cur.clear();
            sort(all(st), [&] (pair <int, int> &A, pair <int, int> &B) {return A.s - A.f < B.s - B.f;});
            for (int i = 0; i * block < sz(st); i++) {
                ls[i].clear(), rs[i].clear();
            }

            for (int i = 0; i < sz(st); i++) {
                int id = i / block;
                ls[id].pb(st[i].f);
                rs[id].pb(st[i].s);
            }

            for (int i = 0; i * block < sz(st); i++) {
                sort(all(ls[i]));
                sort(all(rs[i]));
            }
        }  
    }

    int cal(int l, int r, int k) {
        if (r - l + 1 < k)
            return 0;

        int ans = 0;
        for (auto x : cur) {
            if (min(r, x.s) - max(l, x.f) + 1 >= k) {
                ans++;
            }
        }

        for (int i = 0; i < sz(st); i += block) {
            int en = min(i + block - 1, sz(st) - 1);
            if (st[i].s - st[i].f + 1 >= k) {
                int bl = i / block;
                ans += (en - i + 1);
                ans -= ls[bl].end() - upper_bound(all(ls[bl]), r - k + 1);
                ans -= lower_bound(all(rs[bl]), l + k - 1) - rs[bl].begin();
            } else if (st[en].s - st[en].f + 1 >= k) {
                for (int j = i; j <= en; j++) {
                    if (min(st[j].s, r) - max(st[j].f, l) + 1 >= k)
                        ans++;
                }
            }
        }

        return ans;
    }
} good, bad;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, ss;
    cin >> n >> ss;
    int id = 1;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;

        if (t == 1) {
            cin >> l[id] >> r[id];
            l[id] ^= (ans * ss), r[id] ^= (ans * ss);
            if (l[id] > r[id])
                swap(l[id], r[id]);

            good.add(l[id], r[id]);
            id++;
        }

        if (t == 2) {
            int tt;
            cin >> tt;
            bad.add(l[tt], r[tt]);
        }

        if (t == 3) {
            int l, r, k;
            cin >> l >> r >> k;
            l ^= (ans * ss), r ^= (ans * ss);
            if (l > r)
                swap(l, r);

            ans = good.cal(l, r, k) - bad.cal(l, r, k);
            
            cout << ans << "\n";
        }
    }
}

/*
6 1
1 1 2
3 2 4  2
1 3 5
3 2 3 1
2 1
3 0 3 1
*/

/*
6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
*/

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