oj.uz

Submission #682661

# Submission time Handle Problem Language Result Execution time Memory
682661 2023-01-16T17:31:47 Z phoenix Segments (IZhO18_segments) C++17
15 / 100
 868 ms 9088 KB 
#include<bits/stdc++.h>

using namespace std;

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

void UGABUGA(bool f) {
    if(!f) 1 / 0;
}

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++;
        }
        UGABUGA(pos_arr < (int)arr[block].size() && equal(arr[block][pos_arr], obj(key, val)));
        arr[block].erase(arr[block].begin() + pos_arr);
        UGABUGA(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();
        }
    }
}

Compilation message

segments.cpp: In function 'void UGABUGA(bool)':
segments.cpp:9:14: warning: division by zero [-Wdiv-by-zero]
    9 |     if(!f) 1 / 0;
      |            ~~^~~
segments.cpp:9:14: warning: statement has no effect [-Wunused-value]

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 22 ms 504 KB Output is correct
6 Correct 16 ms 512 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 16 ms 540 KB Output is correct
9 Correct 16 ms 556 KB Output is correct
10 Correct 19 ms 596 KB Output is correct
11 Correct 14 ms 544 KB Output is correct
12 Correct 12 ms 536 KB Output is correct
13 Correct 17 ms 492 KB Output is correct
14 Correct 15 ms 468 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 13 ms 440 KB Output is correct
18 Runtime error 18 ms 1108 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 4016 KB Output is correct
2 Correct 739 ms 3868 KB Output is correct
3 Correct 781 ms 3980 KB Output is correct
4 Correct 796 ms 4092 KB Output is correct
5 Correct 867 ms 6412 KB Output is correct
6 Correct 795 ms 6652 KB Output is correct
7 Correct 747 ms 3980 KB Output is correct
8 Correct 763 ms 3780 KB Output is correct
9 Correct 732 ms 3892 KB Output is correct
10 Correct 506 ms 2064 KB Output is correct
11 Correct 568 ms 2444 KB Output is correct
12 Correct 848 ms 5324 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 976 KB Output is correct
2 Correct 46 ms 1024 KB Output is correct
3 Correct 88 ms 1096 KB Output is correct
4 Correct 48 ms 984 KB Output is correct
5 Correct 868 ms 5460 KB Output is correct
6 Correct 839 ms 4300 KB Output is correct
7 Correct 864 ms 4996 KB Output is correct
8 Correct 838 ms 6676 KB Output is correct
9 Runtime error 758 ms 9088 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 980 KB Output is correct
2 Correct 44 ms 1024 KB Output is correct
3 Correct 45 ms 988 KB Output is correct
4 Correct 53 ms 996 KB Output is correct
5 Correct 857 ms 5596 KB Output is correct
6 Correct 394 ms 1788 KB Output is correct
7 Correct 836 ms 5940 KB Output is correct
8 Correct 435 ms 2160 KB Output is correct
9 Runtime error 184 ms 3976 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 22 ms 504 KB Output is correct
6 Correct 16 ms 512 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 16 ms 540 KB Output is correct
9 Correct 16 ms 556 KB Output is correct
10 Correct 19 ms 596 KB Output is correct
11 Correct 14 ms 544 KB Output is correct
12 Correct 12 ms 536 KB Output is correct
13 Correct 17 ms 492 KB Output is correct
14 Correct 15 ms 468 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 13 ms 440 KB Output is correct
18 Runtime error 18 ms 1108 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 22 ms 504 KB Output is correct
6 Correct 16 ms 512 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 16 ms 540 KB Output is correct
9 Correct 16 ms 556 KB Output is correct
10 Correct 19 ms 596 KB Output is correct
11 Correct 14 ms 544 KB Output is correct
12 Correct 12 ms 536 KB Output is correct
13 Correct 17 ms 492 KB Output is correct
14 Correct 15 ms 468 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 13 ms 440 KB Output is correct
18 Runtime error 18 ms 1108 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -