oj.uz

Submission #682660

# Submission time Handle Problem Language Result Execution time Memory
682660 2023-01-16T17:29:55 Z phoenix Segments (IZhO18_segments) C++17
15 / 100
 870 ms 10392 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 100000;
const int B = 1288;

struct SQRT {
    struct obj {
        int key;
        int val;
        obj(int key, int val) : key(key), val(val) {}
    };
    bool equal(obj a, obj b) {
        return (a.key == b.key && a.val == b.val);
    }
    vector<obj> arr[N / B + 5];
    vector<int> st[N / B + 5];
    int sz = 0, b_num = 0;
    void add(int key, int val) {
        int block = 0;
        while(block < b_num - 1 && (arr[block + 1].empty() || arr[block + 1].front().key < key)) 
            block++;
        int pos_arr = 0, pos_st = 0;
        for(int i = 0; i < (int)arr[block].size(); i++) {
            if(arr[block][i].key < key) pos_arr++;
            if(st[block][i] < val) pos_st++;
        }
        if(!sz) b_num = 1;
        sz++;
        st[block].insert(st[block].begin() + pos_st, val);
        arr[block].insert(arr[block].begin() + pos_arr, obj(key, val));
    }
    void del(int key, int val) {
        int block = 0;
        while(block < b_num - 1 && (arr[block + 1].empty() || arr[block + 1].front().key < key)) 
            block++;
        int pos_arr = 0, pos_st = 0;
        for(int i = 0; i < (int)arr[block].size(); i++) {
            if(arr[block][i].key < key) pos_arr++;
            if(st[block][i] < val) pos_st++;
        }
        assert(pos_arr < (int)arr[block].size() && equal(arr[block][pos_arr], obj(key, val)));
        arr[block].erase(arr[block].begin() + pos_arr);
        assert(pos_st < (int)st[block].size() && st[block][pos_st] == val);
        st[block].erase(st[block].begin() + pos_st);
        sz--;
        if(!sz) b_num = 0;
    }
    int get(int k, int x) {
        int ans = 0;
        int block_p = b_num - 1;
        while(block_p >= 0 && (arr[block_p].empty() || arr[block_p].front().key >= k)) {
            int lb = -1, rb = arr[block_p].size();
            while(rb - lb > 1) {
                int m = (lb + rb) / 2;
                if(st[block_p][m] < x) lb = m;
                else rb = m;
            }
            ans += lb + 1;
            block_p--;
        }
        if(block_p < 0) return ans;
        int arr_p = arr[block_p].size() - 1;
        while(arr_p >= 0 && arr[block_p][arr_p].key >= k) {
            ans += (arr[block_p][arr_p].val < x);
            arr_p--;
        }
        return ans;
    }
    void normalize() {
        vector<obj> v;
        for(int i = 0; i < b_num; i++) {
            for(obj x : arr[i]) 
                v.push_back(x);
        }
        for(int i = 0; i < sz; i++) {
            if(i % B == 0 && !arr[i / B].empty()) {
                arr[i / B].clear();
                st[i / B].clear();
            }
            arr[i / B].push_back(v[i]);
            st[i / B].push_back(v[i].val);
        }
        b_num = (sz - 1) / B + 1;
        for(int i = 0; i < b_num; i++) 
            sort(st[i].begin(), st[i].end());
    }
};

SQRT ll, rr;
int lastans;

vector<pair<int, int>> v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    v.push_back({-1, -1});

    int n, t;
    cin >> n >> t;
    for(int iter = 1; iter <= n; iter++) {
        int type;
        cin >> type;
        if(type == 1) {
            int l, r;
            cin >> l >> r;
            l = (l ^ (t * lastans));
            r = (r ^ (t * lastans));
            if(l > r) swap(l, r);
            v.push_back({l, r});
            int len = r - l + 1;
            ll.add(len, l);
            rr.add(len, r);
        }
        if(type == 2) {
            int id;
            cin >> id;
            ll.del(v[id].second - v[id].first + 1, v[id].first);
            rr.del(v[id].second - v[id].first + 1, v[id].second);
        }
        if(type == 3) {
            int l, r, k;
            cin >> l >> r >> k;
            l = (l ^ (t * lastans));
            r = (r ^ (t * lastans));
            if(l > r) swap(l, r);
            lastans = 0;
            if(r - l + 1 < k) {
                cout << 0 << '\n';
                continue;
            }
            lastans = ll.get(k, r - k + 2) - rr.get(k, l + k - 1);
            cout << lastans << '\n';
        }
        if(iter % B == 0) {
            ll.normalize();
            rr.normalize();
        }
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 3 ms 464 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Correct 19 ms 596 KB Output is correct
6 Correct 23 ms 660 KB Output is correct
7 Correct 12 ms 472 KB Output is correct
8 Correct 17 ms 596 KB Output is correct
9 Correct 16 ms 640 KB Output is correct
10 Correct 18 ms 596 KB Output is correct
11 Correct 13 ms 596 KB Output is correct
12 Correct 13 ms 596 KB Output is correct
13 Correct 18 ms 596 KB Output is correct
14 Correct 14 ms 596 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 12 ms 468 KB Output is correct
18 Runtime error 17 ms 1100 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 744 ms 5060 KB Output is correct
2 Correct 731 ms 5100 KB Output is correct
3 Correct 743 ms 5104 KB Output is correct
4 Correct 795 ms 5416 KB Output is correct
5 Correct 848 ms 7756 KB Output is correct
6 Correct 769 ms 8904 KB Output is correct
7 Correct 737 ms 6648 KB Output is correct
8 Correct 742 ms 6504 KB Output is correct
9 Correct 749 ms 6656 KB Output is correct
10 Correct 441 ms 5020 KB Output is correct
11 Correct 523 ms 5444 KB Output is correct
12 Correct 858 ms 7796 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2352 KB Output is correct
2 Correct 44 ms 2312 KB Output is correct
3 Correct 90 ms 2388 KB Output is correct
4 Correct 44 ms 2308 KB Output is correct
5 Correct 870 ms 6804 KB Output is correct
6 Correct 803 ms 5648 KB Output is correct
7 Correct 861 ms 6368 KB Output is correct
8 Correct 824 ms 7776 KB Output is correct
9 Runtime error 690 ms 10392 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2248 KB Output is correct
2 Correct 46 ms 2244 KB Output is correct
3 Correct 46 ms 2372 KB Output is correct
4 Correct 55 ms 2392 KB Output is correct
5 Correct 850 ms 7036 KB Output is correct
6 Correct 347 ms 4648 KB Output is correct
7 Correct 834 ms 8288 KB Output is correct
8 Correct 450 ms 5052 KB Output is correct
9 Runtime error 175 ms 4984 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 3 ms 464 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Correct 19 ms 596 KB Output is correct
6 Correct 23 ms 660 KB Output is correct
7 Correct 12 ms 472 KB Output is correct
8 Correct 17 ms 596 KB Output is correct
9 Correct 16 ms 640 KB Output is correct
10 Correct 18 ms 596 KB Output is correct
11 Correct 13 ms 596 KB Output is correct
12 Correct 13 ms 596 KB Output is correct
13 Correct 18 ms 596 KB Output is correct
14 Correct 14 ms 596 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 12 ms 468 KB Output is correct
18 Runtime error 17 ms 1100 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 3 ms 464 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Correct 19 ms 596 KB Output is correct
6 Correct 23 ms 660 KB Output is correct
7 Correct 12 ms 472 KB Output is correct
8 Correct 17 ms 596 KB Output is correct
9 Correct 16 ms 640 KB Output is correct
10 Correct 18 ms 596 KB Output is correct
11 Correct 13 ms 596 KB Output is correct
12 Correct 13 ms 596 KB Output is correct
13 Correct 18 ms 596 KB Output is correct
14 Correct 14 ms 596 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 12 ms 468 KB Output is correct
18 Runtime error 17 ms 1100 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -