oj.uz

Submission #879496

# Submission time Handle Problem Language Result Execution time Memory
879496 2023-11-27T14:42:35 Z TheSahib Segments (IZhO18_segments) C++14
7 / 100
 1855 ms 45388 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 + 1e8;
const int MAX = 2e5 + 5;
const int BLOCK = 0;

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;
    c.a.resize(a.a.size() + b.a.size());
    c.b.resize(a.b.size() + b.b.size());
    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.clear();
        tree[node].b.clear();
        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 = 1; i < nxt; i++)
    {
        if(arr[i].first == -1) continue;
        v.push_back(arr[i]);
    }
    cout << '\n';
    sort(all(v));
    build(0, 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(0, 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(0, 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 5 ms 19036 KB Output is correct
2 Correct 4 ms 19288 KB Output is correct
3 Correct 12 ms 19292 KB Output is correct
4 Correct 12 ms 19292 KB Output is correct
5 Correct 11 ms 20060 KB Output is correct
6 Correct 12 ms 20060 KB Output is correct
7 Correct 130 ms 19544 KB Output is correct
8 Correct 315 ms 20536 KB Output is correct
9 Correct 302 ms 20056 KB Output is correct
10 Correct 146 ms 20548 KB Output is correct
11 Correct 14 ms 19804 KB Output is correct
12 Correct 15 ms 19908 KB Output is correct
13 Correct 163 ms 20572 KB Output is correct
14 Correct 304 ms 20124 KB Output is correct
15 Correct 16 ms 19796 KB Output is correct
16 Correct 19 ms 19292 KB Output is correct
17 Correct 233 ms 19824 KB Output is correct
18 Correct 218 ms 20464 KB Output is correct
19 Correct 247 ms 19784 KB Output is correct
20 Correct 256 ms 20052 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 34440 KB Output is correct
2 Correct 267 ms 34244 KB Output is correct
3 Correct 292 ms 34684 KB Output is correct
4 Correct 266 ms 35668 KB Output is correct
5 Runtime error 144 ms 45388 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 21584 KB Output is correct
2 Correct 421 ms 21340 KB Output is correct
3 Correct 1855 ms 21824 KB Output is correct
4 Correct 496 ms 21696 KB Output is correct
5 Correct 202 ms 39552 KB Output is correct
6 Correct 220 ms 36844 KB Output is correct
7 Correct 222 ms 38444 KB Output is correct
8 Runtime error 138 ms 45208 KB Memory limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 21856 KB Output is correct
2 Correct 462 ms 21560 KB Output is correct
3 Correct 471 ms 21588 KB Output is correct
4 Correct 614 ms 21740 KB Output is correct
5 Runtime error 202 ms 41028 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19036 KB Output is correct
2 Correct 4 ms 19288 KB Output is correct
3 Correct 12 ms 19292 KB Output is correct
4 Correct 12 ms 19292 KB Output is correct
5 Correct 11 ms 20060 KB Output is correct
6 Correct 12 ms 20060 KB Output is correct
7 Correct 130 ms 19544 KB Output is correct
8 Correct 315 ms 20536 KB Output is correct
9 Correct 302 ms 20056 KB Output is correct
10 Correct 146 ms 20548 KB Output is correct
11 Correct 14 ms 19804 KB Output is correct
12 Correct 15 ms 19908 KB Output is correct
13 Correct 163 ms 20572 KB Output is correct
14 Correct 304 ms 20124 KB Output is correct
15 Correct 16 ms 19796 KB Output is correct
16 Correct 19 ms 19292 KB Output is correct
17 Correct 233 ms 19824 KB Output is correct
18 Correct 218 ms 20464 KB Output is correct
19 Correct 247 ms 19784 KB Output is correct
20 Correct 256 ms 20052 KB Output is correct
21 Correct 282 ms 34440 KB Output is correct
22 Correct 267 ms 34244 KB Output is correct
23 Correct 292 ms 34684 KB Output is correct
24 Correct 266 ms 35668 KB Output is correct
25 Runtime error 144 ms 45388 KB Memory limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19036 KB Output is correct
2 Correct 4 ms 19288 KB Output is correct
3 Correct 12 ms 19292 KB Output is correct
4 Correct 12 ms 19292 KB Output is correct
5 Correct 11 ms 20060 KB Output is correct
6 Correct 12 ms 20060 KB Output is correct
7 Correct 130 ms 19544 KB Output is correct
8 Correct 315 ms 20536 KB Output is correct
9 Correct 302 ms 20056 KB Output is correct
10 Correct 146 ms 20548 KB Output is correct
11 Correct 14 ms 19804 KB Output is correct
12 Correct 15 ms 19908 KB Output is correct
13 Correct 163 ms 20572 KB Output is correct
14 Correct 304 ms 20124 KB Output is correct
15 Correct 16 ms 19796 KB Output is correct
16 Correct 19 ms 19292 KB Output is correct
17 Correct 233 ms 19824 KB Output is correct
18 Correct 218 ms 20464 KB Output is correct
19 Correct 247 ms 19784 KB Output is correct
20 Correct 256 ms 20052 KB Output is correct
21 Correct 282 ms 34440 KB Output is correct
22 Correct 267 ms 34244 KB Output is correct
23 Correct 292 ms 34684 KB Output is correct
24 Correct 266 ms 35668 KB Output is correct
25 Runtime error 144 ms 45388 KB Memory limit exceeded
26 Halted 0 ms 0 KB -