Submission #174434

#	Time	Username	Problem	Language	Result	Execution time	Memory
174434		mcdx9524	Segments (IZhO18_segments)	C++14	75 / 100	5085 ms	6336 KiB

segments

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return uniform_int_distribution <int> (l, r) (rnd);
}

const int N = 5e3 + 7;

int t, a, b, l, r, k;
int cur_id, id;

struct ev {
    int l, r, id;
};

int inter(int &l, int &r, int &a, int &b) {
    return max(0, min(r, b) - max(l, a) + 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, tp;
    cin >> n >> tp;
    int last_ans = 0;
    vector <ev> seg;
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (t == 1) {
            cin >> a >> b;
            l = a ^ (tp * last_ans);
            r = b ^ (tp * last_ans);
            if (l > r) {
                swap(l, r);
            }
            cur_id++;
            seg.push_back({l, r, cur_id});
        } else if (t == 2) {
            cin >> id;
            for (int j = 0; j < (int) seg.size(); j++) {
                if (seg[j].id == id) {
                    seg.erase(seg.begin() + j);
                    break;
                }
            }
        } else {
            cin >> a >> b >> k;
            l = a ^ (tp * last_ans);
            r = b ^ (tp * last_ans);
            if (l > r) {
                swap(l, r);
            }
            last_ans = 0;
            for (int j = 0; j < (int) seg.size(); j++) {
                if (inter(seg[j].l, seg[j].r, l, r) >= k) {
                    last_ans++;
                }
            }
            cout << last_ans << '\n';
        }
    }
    return 0;
}

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