Submission #652161

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
652161	2022-10-21T14:22:38 Z	vovik	Segments (IZhO18_segments)	C++17	16 / 100	1321 ms	23328 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 = 4000;

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	9812 KB	Output is correct
3	Incorrect	24 ms	9812 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1037 ms	17264 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	321 ms	10688 KB	Output is correct
2	Correct	306 ms	10812 KB	Output is correct
3	Correct	358 ms	10696 KB	Output is correct
4	Correct	306 ms	10736 KB	Output is correct
5	Correct	1106 ms	20224 KB	Output is correct
6	Correct	1149 ms	18980 KB	Output is correct
7	Correct	1079 ms	19616 KB	Output is correct
8	Correct	845 ms	23328 KB	Output is correct
9	Correct	841 ms	22920 KB	Output is correct
10	Correct	882 ms	19552 KB	Output is correct
11	Correct	494 ms	11380 KB	Output is correct
12	Correct	817 ms	20072 KB	Output is correct
13	Correct	857 ms	18800 KB	Output is correct
14	Correct	699 ms	14536 KB	Output is correct
15	Correct	663 ms	14184 KB	Output is correct
16	Correct	597 ms	12972 KB	Output is correct
17	Correct	1307 ms	17324 KB	Output is correct
18	Correct	1291 ms	17320 KB	Output is correct
19	Correct	1292 ms	17428 KB	Output is correct
20	Correct	1321 ms	17420 KB	Output is correct
21	Correct	519 ms	11612 KB	Output is correct
22	Correct	721 ms	15812 KB	Output is correct
23	Correct	765 ms	18232 KB	Output is correct
24	Correct	705 ms	16272 KB	Output is correct
25	Correct	321 ms	10852 KB	Output is correct
26	Correct	301 ms	10852 KB	Output is correct
27	Correct	328 ms	10824 KB	Output is correct
28	Correct	313 ms	10776 KB	Output is correct
29	Correct	770 ms	18376 KB	Output is correct
30	Correct	781 ms	18468 KB	Output is correct
31	Correct	759 ms	23200 KB	Output is correct
32	Correct	793 ms	19568 KB	Output is correct
33	Correct	765 ms	19556 KB	Output is correct
34	Correct	606 ms	14088 KB	Output is correct
35	Correct	759 ms	17540 KB	Output is correct
36	Correct	781 ms	19396 KB	Output is correct