Submission #652156

#	Time	Username	Problem	Language	Result	Execution time	Memory
652156		vovik	Segments (IZhO18_segments)	C++17	75 / 100	5058 ms	22528 KiB

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 = 2000, 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;
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();
    for (int i = k / K + 1; i <= N / K; ++i) ans += ls[i].size();
    for (int i = k / K + 1; i <= N / K; ++i) ans -= ls[i].end() - lower_bound(ls[i].begin(), ls[i].end(), dl);
    for (int i = k / K + 1; i <= N / K; ++i) ans -= upper_bound(rs[i].begin(), rs[i].end(), dr) - rs[i].begin();
    for (int len = k; len < (k / K + 1) * K; ++len) ans += self_l[len].size();
    for (int len = k; len < (k / K + 1) * K; ++len) ans -= self_l[len].end() - lower_bound(self_l[len].begin(), self_l[len].end(), dl);
    for (int len = k; len < (k / K + 1) * K; ++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()), 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 = 3000;

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: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 0 / 25