Submission #1083514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083514		LOLOLO	Segments (IZhO18_segments)	C++17	75 / 100	5057 ms	7896 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 = 2e5;
int l[N], r[N];

struct {
    vector <pair <int, int>> in;
    vector <int> ls, rs;
    void add(int l, int r) {
        in.pb({l, r});
        if (sz(in) >= block) {
            for (auto x : in) {
                ls.pb(x.f);
                rs.pb(x.s);
            }

            in.clear();
            sort(all(ls));
            sort(all(rs));
        } 
    }

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

        int ans = 0;
        int p = upper_bound(all(ls), r - k + 1) - ls.begin();
        ans += sz(ls) - p;

        p = lower_bound(all(rs), l + k - 1) - rs.begin();
        ans += p;

        for (auto x : in) {
            if (min(x.s, r) - max(x.f, l) + 1 < k) 
                ans++;
        }

        return sz(ls) + sz(rs) + sz(in) - 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: 0 / 25