Submission #652163

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
652163	2022-10-21T14:23:15 Z	vovik	Segments (IZhO18_segments)	C++17	16 / 100	1140 ms	23448 KB

segments

//Bitch, я поймал свой balance
//Теперь нихуя не надо делать
#include <bits/stdc++.h>

#define vc vector

using namespace std;
typedef long long ll;

#define X first
#define Y second

const int K = 600, N = 2e5 + 5;

vc<int> ls[N / K + 1];
vc<int> rs[N / K + 1];
vc<int> self_l[N];
vc<int> self_r[N];

vc<int> e, all;
int get(int L, int R, int k) {
    int dl = R - k + 2, dr = L + k - 2;
    //for l [dl; inf]
    //for r [-inf; dr]
    int ans = 0;
    k = lower_bound(e.begin(), e.end(), k) - e.begin();
    int e1 = N / K, e2 = (k / K + 1) * K;
    ans += all.end() - lower_bound(all.begin(), all.end(), k);
    for (int i = k / K + 1; i <= e1; ++i) ans -= ls[i].end() - lower_bound(ls[i].begin(), ls[i].end(), dl);
    for (int i = k / K + 1; i <= e1; ++i) ans -= upper_bound(rs[i].begin(), rs[i].end(), dr) - rs[i].begin();
    for (int len = k; len < e2; ++len) ans -= self_l[len].end() - lower_bound(self_l[len].begin(), self_l[len].end(), dl);
    for (int len = k; len < e2; ++len) ans -= upper_bound(self_r[len].begin(), self_r[len].end(), dr) - self_r[len].begin();
    return ans;
}

void rebuild(multiset<pair<int, int>> &x) {
    e.clear();
    for (auto &i : ls) i.clear();
    for (auto &i : rs) i.clear();
    for (auto &i : self_l) i.clear();
    for (auto &i : self_r) i.clear();
    for (auto [l, r] : x) e.push_back(r - l + 1);
    sort(e.begin(), e.end()), all = e, e.resize(unique(e.begin(), e.end()) - e.begin());
    for (auto [l, r] : x) {
        int len = r - l + 1;
        len = lower_bound(e.begin(), e.end(), len) - e.begin();
        ls[len / K].push_back(l), rs[len / K].push_back(r);
        self_l[len].push_back(l);
        self_r[len].push_back(r);
    }
    for (auto &i : self_l) sort(i.begin(), i.end());
    for (auto &i : self_r) sort(i.begin(), i.end());
    for (auto &i : ls) sort(i.begin(), i.end());
    for (auto &i : rs) sort(i.begin(), i.end());
}

const int E = 7000;

int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int n, T;
    cin >> n >> T;
    multiset<pair<int, int>> x;
    vc<pair<int, int>> f;
    vc<pair<int, int>> rec_add, rec_del;
    int lst = 0;
    for (int a, b, t, id, k; n--;) {
        if (n % E == 0) rec_add.clear(), rec_del.clear(), rebuild(x);
        cin >> t;
        if (t == 1) {
            cin >> a >> b;
            int l = (T * lst) ^ a, r = (T * lst) ^ b;
            if (l > r) swap(l, r);
            f.emplace_back(l, r);
            x.insert(f.back());
            rec_add.push_back(f.back());
        } else if (t == 2) {
            cin >> id, --id;
            x.erase(x.find(f[id]));
            rec_del.push_back(f[id]);
        } else if (t == 3) {
            cin >> a >> b >> k;
            int l = (T * lst) ^ a, r = (T * lst) ^ b;
            if (l > r) swap(l, r);
            lst = 0;
            int dl = r - k + 2, dr = l + k - 2;
            //for l [dl; inf]
            //for r [-inf; dr]

            lst = get(l, r, k);

            for (auto [l, r] : rec_add) if (r - l + 1 >= k) ++lst, lst -= (l >= dl), lst -= (r <= dr);
            for (auto [l, r] : rec_del) if (r - l + 1 >= k) --lst, lst += (l >= dl), lst += (r <= dr);
            cout << lst << '\n';
        }
    }
}

Subtask #1
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9684 KB	Output is correct
2	Correct	7 ms	9676 KB	Output is correct
3	Incorrect	24 ms	9884 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	942 ms	17200 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	343 ms	10696 KB	Output is correct
2	Correct	325 ms	10656 KB	Output is correct
3	Correct	381 ms	10824 KB	Output is correct
4	Correct	340 ms	10776 KB	Output is correct
5	Correct	840 ms	20148 KB	Output is correct
6	Correct	949 ms	18756 KB	Output is correct
7	Correct	915 ms	19848 KB	Output is correct
8	Correct	574 ms	23448 KB	Output is correct
9	Correct	545 ms	22976 KB	Output is correct
10	Correct	602 ms	19912 KB	Output is correct
11	Correct	486 ms	11152 KB	Output is correct
12	Correct	615 ms	19844 KB	Output is correct
13	Correct	605 ms	18400 KB	Output is correct
14	Correct	574 ms	14228 KB	Output is correct
15	Correct	556 ms	13812 KB	Output is correct
16	Correct	541 ms	12676 KB	Output is correct
17	Correct	1028 ms	17184 KB	Output is correct
18	Correct	1121 ms	17052 KB	Output is correct
19	Correct	1140 ms	16976 KB	Output is correct
20	Correct	1114 ms	17028 KB	Output is correct
21	Correct	528 ms	11340 KB	Output is correct
22	Correct	642 ms	15556 KB	Output is correct
23	Correct	621 ms	17548 KB	Output is correct
24	Correct	594 ms	15728 KB	Output is correct
25	Correct	347 ms	10844 KB	Output is correct
26	Correct	326 ms	10516 KB	Output is correct
27	Correct	349 ms	10480 KB	Output is correct
28	Correct	335 ms	10508 KB	Output is correct
29	Correct	630 ms	18356 KB	Output is correct
30	Correct	620 ms	18428 KB	Output is correct
31	Correct	488 ms	22660 KB	Output is correct
32	Correct	620 ms	19288 KB	Output is correct
33	Correct	606 ms	18732 KB	Output is correct
34	Correct	562 ms	13668 KB	Output is correct
35	Correct	627 ms	16832 KB	Output is correct
36	Correct	587 ms	18996 KB	Output is correct