oj.uz

Submission #682662

# Submission time Handle Problem Language Result Execution time Memory
682662 2023-01-16T17:32:45 Z phoenix Segments (IZhO18_segments) C++17
15 / 100
 5000 ms 6508 KB 
#include<bits/stdc++.h>

using namespace std;

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

void UGABUGA(bool f) {
    if(!f) {
        while(1) {
            
        }
    }
}

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();
        }
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 17 ms 528 KB Output is correct
6 Correct 21 ms 548 KB Output is correct
7 Correct 8 ms 340 KB Output is correct
8 Correct 16 ms 540 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 18 ms 496 KB Output is correct
11 Correct 12 ms 468 KB Output is correct
12 Correct 13 ms 500 KB Output is correct
13 Correct 20 ms 596 KB Output is correct
14 Correct 18 ms 536 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 340 KB Output is correct
18 Execution timed out 5039 ms 544 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 3916 KB Output is correct
2 Correct 738 ms 3804 KB Output is correct
3 Correct 745 ms 3796 KB Output is correct
4 Correct 767 ms 4096 KB Output is correct
5 Correct 781 ms 6420 KB Output is correct
6 Correct 758 ms 6508 KB Output is correct
7 Correct 759 ms 3876 KB Output is correct
8 Correct 733 ms 3924 KB Output is correct
9 Correct 734 ms 3900 KB Output is correct
10 Correct 434 ms 2164 KB Output is correct
11 Correct 517 ms 2440 KB Output is correct
12 Correct 879 ms 5304 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 1096 KB Output is correct
2 Correct 40 ms 1072 KB Output is correct
3 Correct 96 ms 1032 KB Output is correct
4 Correct 43 ms 1000 KB Output is correct
5 Correct 840 ms 5352 KB Output is correct
6 Correct 786 ms 4608 KB Output is correct
7 Correct 819 ms 5136 KB Output is correct
8 Correct 771 ms 6440 KB Output is correct
9 Execution timed out 5047 ms 6396 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 980 KB Output is correct
2 Correct 43 ms 1032 KB Output is correct
3 Correct 44 ms 1120 KB Output is correct
4 Correct 52 ms 1040 KB Output is correct
5 Correct 804 ms 5680 KB Output is correct
6 Correct 341 ms 1788 KB Output is correct
7 Correct 798 ms 6032 KB Output is correct
8 Correct 431 ms 2248 KB Output is correct
9 Execution timed out 5062 ms 2724 KB Time limit exceeded
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 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 17 ms 528 KB Output is correct
6 Correct 21 ms 548 KB Output is correct
7 Correct 8 ms 340 KB Output is correct
8 Correct 16 ms 540 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 18 ms 496 KB Output is correct
11 Correct 12 ms 468 KB Output is correct
12 Correct 13 ms 500 KB Output is correct
13 Correct 20 ms 596 KB Output is correct
14 Correct 18 ms 536 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 340 KB Output is correct
18 Execution timed out 5039 ms 544 KB Time limit exceeded
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 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 17 ms 528 KB Output is correct
6 Correct 21 ms 548 KB Output is correct
7 Correct 8 ms 340 KB Output is correct
8 Correct 16 ms 540 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 18 ms 496 KB Output is correct
11 Correct 12 ms 468 KB Output is correct
12 Correct 13 ms 500 KB Output is correct
13 Correct 20 ms 596 KB Output is correct
14 Correct 18 ms 536 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 340 KB Output is correct
18 Execution timed out 5039 ms 544 KB Time limit exceeded
19 Halted 0 ms 0 KB -