oj.uz

Submission #879376

# Submission time Handle Problem Language Result Execution time Memory
879376 2023-11-27T08:41:07 Z TheSahib Segments (IZhO18_segments) C++17
7 / 100
 3847 ms 36948 KB 
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;

const int oo = 2e9 + 9;
const int MAX = 2e5 + 5;
const int BLOCK = 50005;

pii arr[MAX];
int nxt = 1;
vector<pii> v;

struct DATA{
    vector<int> a;
    vector<int> b;
};

DATA combine(DATA& a, DATA& b){
    DATA c;
    int d = a.a.size() + a.b.size();
    c.a.resize(d);
    c.b.resize(d);
    merge(all(a.a), all(b.a), c.a.begin());
    merge(all(a.b), all(b.b), c.b.begin());
    return c;   
}

DATA tree[MAX * 2];

void build(int node, int l, int r){
    if(l == r){
        tree[node].a = {v[l].second};
        tree[node].b = {v[l].second - v[l].first + 1};
        return;
    }
    int mid = (l + r) / 2;
    build(node + 1, l, mid);
    build(node + (mid - l + 1) * 2, mid + 1, r);
    tree[node] = combine(tree[node + 1], tree[node + (mid - l + 1) * 2]);
}

int ask1(int node, int l, int r, int ql, int qr, int val){
    if(ql > r || qr < l) return 0;
    if(ql <= l && r <= qr){
        auto itr = lower_bound(all(tree[node].a), val);
        return (tree[node].a.end() - itr);
    }
    int mid = (l + r) / 2;
    return ask1(node + 1, l, mid, ql, qr, val) + ask1(node + (mid - l + 1) * 2, mid + 1, r, ql, qr, val);
}
int ask2(int node, int l, int r, int ql, int qr, int val){
    if(ql > r || qr < l) return 0;
    if(ql <= l && r <= qr){
        auto itr = lower_bound(all(tree[node].b), val);
        return (tree[node].b.end() - itr);
    }
    int mid = (l + r) / 2;
    return ask2(node + 1, l, mid, ql, qr, val) + ask2(node + (mid - l + 1) * 2, mid + 1, r, ql, qr, val);
}

vector<pii> b1;
vector<pii> b2;

void update(){
    v.clear();
    b1.clear();
    b2.clear();
    for (int i = 0; i < nxt; i++)
    {
        if(arr[i].first == -1) continue;
        v.push_back(arr[i]);
    }
    sort(all(v));
    build(1, 0, v.size() - 1);
}

int f(pii a, pii b){
    int ans = min(a.second, b.second) - max(a.first, b.first) + 1;
    if(ans <= 0) return 0;
    return ans;
}

void solve(){
    int n, o; cin >> n >> o;
    int lastAns = 0;
    while(n--){
        int t; cin >> t;
        if(t == 1){
            int a, b; cin >> a >> b;
            a = a ^ (o * lastAns);
            b = b ^ (o * lastAns);
            if(a > b) swap(a, b);
            arr[nxt++] = {a, b};
            b1.push_back({a, b});
        }
        else if(t == 2){
            int id; cin >> id;
            b2.push_back(arr[id]);
            arr[id] = {-1, -1};
        }
        else{
            int a, b, c; cin >> a >> b >> c;
            a = a ^ (o * lastAns);
            b = b ^ (o * lastAns);
            if(a > b) swap(a, b);
            if(b - a + 1 < c){
                lastAns = 0;
                cout << 0 << '\n';
                continue;
            }
            if(b1.size() + b2.size() > BLOCK){
                update();
            }
            int ans = 0;
            if(v.size() != 0){
                int i = lower_bound(all(v), make_pair(a, -1)) - v.begin();
                if(i > 0){
                    ans += ask1(1, 0, v.size() - 1, 0, i - 1, a + c - 1);
                }
                int j = upper_bound(all(v), make_pair(b - c + 1, oo)) - v.begin();
                if(j > 0 && i <= j - 1){
                    ans += ask2(1, 0, v.size() - 1, i, j - 1, c);
                }
            }
            for(auto p:b1){
                ans += (f(p, {a, b}) >= c);
            }
            for(auto p:b2){
                ans -= (f(p, {a, b}) >= c);
            }
            lastAns = ans;
            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
*/

int main()
{
    solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 13 ms 19260 KB Output is correct
4 Correct 15 ms 19300 KB Output is correct
5 Correct 15 ms 19292 KB Output is correct
6 Correct 17 ms 19360 KB Output is correct
7 Correct 17 ms 19288 KB Output is correct
8 Correct 12 ms 19292 KB Output is correct
9 Correct 14 ms 19416 KB Output is correct
10 Correct 10 ms 19288 KB Output is correct
11 Correct 21 ms 19288 KB Output is correct
12 Correct 21 ms 19288 KB Output is correct
13 Correct 10 ms 19292 KB Output is correct
14 Correct 13 ms 19292 KB Output is correct
15 Correct 13 ms 19292 KB Output is correct
16 Correct 13 ms 19288 KB Output is correct
17 Correct 14 ms 19292 KB Output is correct
18 Correct 10 ms 19292 KB Output is correct
19 Correct 14 ms 19292 KB Output is correct
20 Correct 14 ms 19548 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3847 ms 20568 KB Output is correct
2 Correct 3834 ms 23208 KB Output is correct
3 Correct 3791 ms 23080 KB Output is correct
4 Incorrect 283 ms 36948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 13 ms 19260 KB Output is correct
4 Correct 15 ms 19300 KB Output is correct
5 Correct 15 ms 19292 KB Output is correct
6 Correct 17 ms 19360 KB Output is correct
7 Correct 17 ms 19288 KB Output is correct
8 Correct 12 ms 19292 KB Output is correct
9 Correct 14 ms 19416 KB Output is correct
10 Correct 10 ms 19288 KB Output is correct
11 Correct 21 ms 19288 KB Output is correct
12 Correct 21 ms 19288 KB Output is correct
13 Correct 10 ms 19292 KB Output is correct
14 Correct 13 ms 19292 KB Output is correct
15 Correct 13 ms 19292 KB Output is correct
16 Correct 13 ms 19288 KB Output is correct
17 Correct 14 ms 19292 KB Output is correct
18 Correct 10 ms 19292 KB Output is correct
19 Correct 14 ms 19292 KB Output is correct
20 Correct 14 ms 19548 KB Output is correct
21 Correct 3847 ms 20568 KB Output is correct
22 Correct 3834 ms 23208 KB Output is correct
23 Correct 3791 ms 23080 KB Output is correct
24 Incorrect 283 ms 36948 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 13 ms 19260 KB Output is correct
4 Correct 15 ms 19300 KB Output is correct
5 Correct 15 ms 19292 KB Output is correct
6 Correct 17 ms 19360 KB Output is correct
7 Correct 17 ms 19288 KB Output is correct
8 Correct 12 ms 19292 KB Output is correct
9 Correct 14 ms 19416 KB Output is correct
10 Correct 10 ms 19288 KB Output is correct
11 Correct 21 ms 19288 KB Output is correct
12 Correct 21 ms 19288 KB Output is correct
13 Correct 10 ms 19292 KB Output is correct
14 Correct 13 ms 19292 KB Output is correct
15 Correct 13 ms 19292 KB Output is correct
16 Correct 13 ms 19288 KB Output is correct
17 Correct 14 ms 19292 KB Output is correct
18 Correct 10 ms 19292 KB Output is correct
19 Correct 14 ms 19292 KB Output is correct
20 Correct 14 ms 19548 KB Output is correct
21 Correct 3847 ms 20568 KB Output is correct
22 Correct 3834 ms 23208 KB Output is correct
23 Correct 3791 ms 23080 KB Output is correct
24 Incorrect 283 ms 36948 KB Output isn't correct
25 Halted 0 ms 0 KB -