oj.uz

Submission #879517

# Submission time Handle Problem Language Result Execution time Memory
879517 2023-11-27T15:18:12 Z TheSahib Segments (IZhO18_segments) C++14
7 / 100
 484 ms 45416 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 = 2000;
 
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 = {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(){
    for (int i = 0; i < v.size() * 2; i++)
    {
        tree[i].a.clear();
        tree[i].a.shrink_to_fit();
        tree[i].b.clear();
        tree[i].b.shrink_to_fit();
    }
    
    v.clear();
    b1.clear();
    b2.clear();
    for (int i = 1; i < nxt; i++)
    {
        if(arr[i].first == -1) continue;
        v.push_back(arr[i]);
    }
    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();
}

Compilation message

segments.cpp: In function 'void update()':
segments.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < v.size() * 2; i++)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 13 ms 19060 KB Output is correct
4 Correct 12 ms 19036 KB Output is correct
5 Correct 11 ms 20060 KB Output is correct
6 Correct 12 ms 20056 KB Output is correct
7 Correct 12 ms 19292 KB Output is correct
8 Correct 11 ms 19864 KB Output is correct
9 Correct 12 ms 19548 KB Output is correct
10 Correct 10 ms 20060 KB Output is correct
11 Correct 15 ms 19548 KB Output is correct
12 Correct 15 ms 19548 KB Output is correct
13 Correct 10 ms 20056 KB Output is correct
14 Correct 11 ms 19548 KB Output is correct
15 Correct 11 ms 19036 KB Output is correct
16 Correct 11 ms 19036 KB Output is correct
17 Correct 12 ms 19516 KB Output is correct
18 Correct 10 ms 20060 KB Output is correct
19 Correct 12 ms 19548 KB Output is correct
20 Correct 12 ms 19580 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 31720 KB Output is correct
2 Correct 317 ms 31760 KB Output is correct
3 Correct 304 ms 31916 KB Output is correct
4 Correct 312 ms 33184 KB Output is correct
5 Runtime error 148 ms 43076 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 19532 KB Output is correct
2 Correct 161 ms 19536 KB Output is correct
3 Correct 172 ms 19764 KB Output is correct
4 Correct 163 ms 19540 KB Output is correct
5 Correct 196 ms 37248 KB Output is correct
6 Correct 235 ms 34380 KB Output is correct
7 Correct 256 ms 35652 KB Output is correct
8 Runtime error 135 ms 42944 KB Memory limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 19504 KB Output is correct
2 Correct 165 ms 19536 KB Output is correct
3 Correct 169 ms 19556 KB Output is correct
4 Correct 188 ms 19796 KB Output is correct
5 Correct 201 ms 38464 KB Output is correct
6 Correct 336 ms 22820 KB Output is correct
7 Correct 182 ms 40064 KB Output is correct
8 Correct 329 ms 27216 KB Output is correct
9 Correct 484 ms 30392 KB Output is correct
10 Correct 428 ms 39492 KB Output is correct
11 Correct 335 ms 24404 KB Output is correct
12 Runtime error 165 ms 45416 KB Memory limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 13 ms 19060 KB Output is correct
4 Correct 12 ms 19036 KB Output is correct
5 Correct 11 ms 20060 KB Output is correct
6 Correct 12 ms 20056 KB Output is correct
7 Correct 12 ms 19292 KB Output is correct
8 Correct 11 ms 19864 KB Output is correct
9 Correct 12 ms 19548 KB Output is correct
10 Correct 10 ms 20060 KB Output is correct
11 Correct 15 ms 19548 KB Output is correct
12 Correct 15 ms 19548 KB Output is correct
13 Correct 10 ms 20056 KB Output is correct
14 Correct 11 ms 19548 KB Output is correct
15 Correct 11 ms 19036 KB Output is correct
16 Correct 11 ms 19036 KB Output is correct
17 Correct 12 ms 19516 KB Output is correct
18 Correct 10 ms 20060 KB Output is correct
19 Correct 12 ms 19548 KB Output is correct
20 Correct 12 ms 19580 KB Output is correct
21 Correct 273 ms 31720 KB Output is correct
22 Correct 317 ms 31760 KB Output is correct
23 Correct 304 ms 31916 KB Output is correct
24 Correct 312 ms 33184 KB Output is correct
25 Runtime error 148 ms 43076 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 19032 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 13 ms 19060 KB Output is correct
4 Correct 12 ms 19036 KB Output is correct
5 Correct 11 ms 20060 KB Output is correct
6 Correct 12 ms 20056 KB Output is correct
7 Correct 12 ms 19292 KB Output is correct
8 Correct 11 ms 19864 KB Output is correct
9 Correct 12 ms 19548 KB Output is correct
10 Correct 10 ms 20060 KB Output is correct
11 Correct 15 ms 19548 KB Output is correct
12 Correct 15 ms 19548 KB Output is correct
13 Correct 10 ms 20056 KB Output is correct
14 Correct 11 ms 19548 KB Output is correct
15 Correct 11 ms 19036 KB Output is correct
16 Correct 11 ms 19036 KB Output is correct
17 Correct 12 ms 19516 KB Output is correct
18 Correct 10 ms 20060 KB Output is correct
19 Correct 12 ms 19548 KB Output is correct
20 Correct 12 ms 19580 KB Output is correct
21 Correct 273 ms 31720 KB Output is correct
22 Correct 317 ms 31760 KB Output is correct
23 Correct 304 ms 31916 KB Output is correct
24 Correct 312 ms 33184 KB Output is correct
25 Runtime error 148 ms 43076 KB Memory limit exceeded
26 Halted 0 ms 0 KB -