oj.uz

Submission #682667

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

using namespace std;

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

void UGABUGA(bool f) {
    if(!f) {
        int x = 1;
        while(x) x++;
    }
}

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].empty() || arr[block].back().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].empty() || arr[block].back().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:11:19: warning: iteration 2147483646 invokes undefined behavior [-Waggressive-loop-optimizations]
   11 |         while(x) x++;
      |                  ~^~
segments.cpp:11:15: note: within this loop
   11 |         while(x) x++;
      |               ^

Subtask #1
7.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 16 ms 468 KB Output is correct
6 Correct 15 ms 544 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 15 ms 468 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 17 ms 536 KB Output is correct
11 Correct 13 ms 596 KB Output is correct
12 Correct 13 ms 472 KB Output is correct
13 Correct 17 ms 468 KB Output is correct
14 Correct 14 ms 540 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 12 ms 444 KB Output is correct
18 Correct 17 ms 548 KB Output is correct
19 Correct 13 ms 340 KB Output is correct
20 Correct 13 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 4160 KB Output is correct
2 Correct 721 ms 3868 KB Output is correct
3 Correct 709 ms 3812 KB Output is correct
4 Correct 761 ms 4024 KB Output is correct
5 Correct 765 ms 6528 KB Output is correct
6 Correct 761 ms 6516 KB Output is correct
7 Correct 740 ms 3832 KB Output is correct
8 Correct 740 ms 3920 KB Output is correct
9 Correct 718 ms 3980 KB Output is correct
10 Correct 426 ms 2052 KB Output is correct
11 Correct 527 ms 2504 KB Output is correct
12 Correct 811 ms 5288 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1176 KB Output is correct
2 Correct 40 ms 1004 KB Output is correct
3 Correct 88 ms 1132 KB Output is correct
4 Correct 43 ms 984 KB Output is correct
5 Correct 834 ms 5388 KB Output is correct
6 Correct 794 ms 4416 KB Output is correct
7 Correct 821 ms 5176 KB Output is correct
8 Correct 801 ms 6452 KB Output is correct
9 Correct 779 ms 6228 KB Output is correct
10 Execution timed out 5086 ms 4412 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1036 KB Output is correct
2 Correct 46 ms 952 KB Output is correct
3 Correct 46 ms 1008 KB Output is correct
4 Correct 54 ms 1012 KB Output is correct
5 Correct 812 ms 5768 KB Output is correct
6 Correct 335 ms 1644 KB Output is correct
7 Correct 807 ms 5944 KB Output is correct
8 Correct 447 ms 2412 KB Output is correct
9 Execution timed out 5092 ms 2776 KB Time limit exceeded
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 16 ms 468 KB Output is correct
6 Correct 15 ms 544 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 15 ms 468 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 17 ms 536 KB Output is correct
11 Correct 13 ms 596 KB Output is correct
12 Correct 13 ms 472 KB Output is correct
13 Correct 17 ms 468 KB Output is correct
14 Correct 14 ms 540 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 12 ms 444 KB Output is correct
18 Correct 17 ms 548 KB Output is correct
19 Correct 13 ms 340 KB Output is correct
20 Correct 13 ms 340 KB Output is correct
21 Correct 736 ms 4160 KB Output is correct
22 Correct 721 ms 3868 KB Output is correct
23 Correct 709 ms 3812 KB Output is correct
24 Correct 761 ms 4024 KB Output is correct
25 Correct 765 ms 6528 KB Output is correct
26 Correct 761 ms 6516 KB Output is correct
27 Correct 740 ms 3832 KB Output is correct
28 Correct 740 ms 3920 KB Output is correct
29 Correct 718 ms 3980 KB Output is correct
30 Correct 426 ms 2052 KB Output is correct
31 Correct 527 ms 2504 KB Output is correct
32 Correct 811 ms 5288 KB Output is correct
33 Correct 43 ms 1036 KB Output is correct
34 Correct 46 ms 952 KB Output is correct
35 Correct 46 ms 1008 KB Output is correct
36 Correct 54 ms 1012 KB Output is correct
37 Correct 812 ms 5768 KB Output is correct
38 Correct 335 ms 1644 KB Output is correct
39 Correct 807 ms 5944 KB Output is correct
40 Correct 447 ms 2412 KB Output is correct
41 Execution timed out 5092 ms 2776 KB Time limit exceeded
42 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 16 ms 468 KB Output is correct
6 Correct 15 ms 544 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 15 ms 468 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 17 ms 536 KB Output is correct
11 Correct 13 ms 596 KB Output is correct
12 Correct 13 ms 472 KB Output is correct
13 Correct 17 ms 468 KB Output is correct
14 Correct 14 ms 540 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 12 ms 444 KB Output is correct
18 Correct 17 ms 548 KB Output is correct
19 Correct 13 ms 340 KB Output is correct
20 Correct 13 ms 340 KB Output is correct
21 Correct 736 ms 4160 KB Output is correct
22 Correct 721 ms 3868 KB Output is correct
23 Correct 709 ms 3812 KB Output is correct
24 Correct 761 ms 4024 KB Output is correct
25 Correct 765 ms 6528 KB Output is correct
26 Correct 761 ms 6516 KB Output is correct
27 Correct 740 ms 3832 KB Output is correct
28 Correct 740 ms 3920 KB Output is correct
29 Correct 718 ms 3980 KB Output is correct
30 Correct 426 ms 2052 KB Output is correct
31 Correct 527 ms 2504 KB Output is correct
32 Correct 811 ms 5288 KB Output is correct
33 Correct 61 ms 1176 KB Output is correct
34 Correct 40 ms 1004 KB Output is correct
35 Correct 88 ms 1132 KB Output is correct
36 Correct 43 ms 984 KB Output is correct
37 Correct 834 ms 5388 KB Output is correct
38 Correct 794 ms 4416 KB Output is correct
39 Correct 821 ms 5176 KB Output is correct
40 Correct 801 ms 6452 KB Output is correct
41 Correct 779 ms 6228 KB Output is correct
42 Execution timed out 5086 ms 4412 KB Time limit exceeded
43 Halted 0 ms 0 KB -