oj.uz

답안 #682672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682672 2023-01-16T17:50:42 Z phoenix Segments (IZhO18_segments) C++17
22 / 100
 811 ms 6028 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 200000;
const int B = 1800;

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

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++;
        }
        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
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 20 ms 568 KB Output is correct
6 Correct 25 ms 496 KB Output is correct
7 Correct 8 ms 396 KB Output is correct
8 Correct 31 ms 504 KB Output is correct
9 Correct 19 ms 468 KB Output is correct
10 Correct 23 ms 556 KB Output is correct
11 Correct 14 ms 500 KB Output is correct
12 Correct 14 ms 524 KB Output is correct
13 Correct 22 ms 596 KB Output is correct
14 Correct 18 ms 528 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 12 ms 340 KB Output is correct
18 Correct 22 ms 524 KB Output is correct
19 Correct 14 ms 444 KB Output is correct
20 Correct 15 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 685 ms 3676 KB Output is correct
2 Correct 743 ms 3644 KB Output is correct
3 Correct 704 ms 3896 KB Output is correct
4 Correct 699 ms 3768 KB Output is correct
5 Correct 806 ms 5844 KB Output is correct
6 Correct 768 ms 6024 KB Output is correct
7 Correct 683 ms 3580 KB Output is correct
8 Correct 691 ms 3548 KB Output is correct
9 Correct 711 ms 3724 KB Output is correct
10 Correct 409 ms 2452 KB Output is correct
11 Correct 510 ms 2408 KB Output is correct
12 Correct 810 ms 4868 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 1076 KB Output is correct
2 Correct 40 ms 1044 KB Output is correct
3 Correct 90 ms 1076 KB Output is correct
4 Correct 60 ms 988 KB Output is correct
5 Correct 771 ms 4984 KB Output is correct
6 Correct 738 ms 4000 KB Output is correct
7 Correct 758 ms 4744 KB Output is correct
8 Correct 811 ms 5732 KB Output is correct
9 Correct 771 ms 5496 KB Output is correct
10 Runtime error 498 ms 6028 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 932 KB Output is correct
2 Correct 46 ms 1056 KB Output is correct
3 Correct 46 ms 952 KB Output is correct
4 Correct 69 ms 1128 KB Output is correct
5 Correct 779 ms 5112 KB Output is correct
6 Correct 360 ms 1772 KB Output is correct
7 Correct 795 ms 5340 KB Output is correct
8 Correct 433 ms 2176 KB Output is correct
9 Runtime error 282 ms 3860 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 20 ms 568 KB Output is correct
6 Correct 25 ms 496 KB Output is correct
7 Correct 8 ms 396 KB Output is correct
8 Correct 31 ms 504 KB Output is correct
9 Correct 19 ms 468 KB Output is correct
10 Correct 23 ms 556 KB Output is correct
11 Correct 14 ms 500 KB Output is correct
12 Correct 14 ms 524 KB Output is correct
13 Correct 22 ms 596 KB Output is correct
14 Correct 18 ms 528 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 12 ms 340 KB Output is correct
18 Correct 22 ms 524 KB Output is correct
19 Correct 14 ms 444 KB Output is correct
20 Correct 15 ms 340 KB Output is correct
21 Correct 685 ms 3676 KB Output is correct
22 Correct 743 ms 3644 KB Output is correct
23 Correct 704 ms 3896 KB Output is correct
24 Correct 699 ms 3768 KB Output is correct
25 Correct 806 ms 5844 KB Output is correct
26 Correct 768 ms 6024 KB Output is correct
27 Correct 683 ms 3580 KB Output is correct
28 Correct 691 ms 3548 KB Output is correct
29 Correct 711 ms 3724 KB Output is correct
30 Correct 409 ms 2452 KB Output is correct
31 Correct 510 ms 2408 KB Output is correct
32 Correct 810 ms 4868 KB Output is correct
33 Correct 43 ms 932 KB Output is correct
34 Correct 46 ms 1056 KB Output is correct
35 Correct 46 ms 952 KB Output is correct
36 Correct 69 ms 1128 KB Output is correct
37 Correct 779 ms 5112 KB Output is correct
38 Correct 360 ms 1772 KB Output is correct
39 Correct 795 ms 5340 KB Output is correct
40 Correct 433 ms 2176 KB Output is correct
41 Runtime error 282 ms 3860 KB Execution killed with signal 6
42 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 20 ms 568 KB Output is correct
6 Correct 25 ms 496 KB Output is correct
7 Correct 8 ms 396 KB Output is correct
8 Correct 31 ms 504 KB Output is correct
9 Correct 19 ms 468 KB Output is correct
10 Correct 23 ms 556 KB Output is correct
11 Correct 14 ms 500 KB Output is correct
12 Correct 14 ms 524 KB Output is correct
13 Correct 22 ms 596 KB Output is correct
14 Correct 18 ms 528 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 12 ms 340 KB Output is correct
18 Correct 22 ms 524 KB Output is correct
19 Correct 14 ms 444 KB Output is correct
20 Correct 15 ms 340 KB Output is correct
21 Correct 685 ms 3676 KB Output is correct
22 Correct 743 ms 3644 KB Output is correct
23 Correct 704 ms 3896 KB Output is correct
24 Correct 699 ms 3768 KB Output is correct
25 Correct 806 ms 5844 KB Output is correct
26 Correct 768 ms 6024 KB Output is correct
27 Correct 683 ms 3580 KB Output is correct
28 Correct 691 ms 3548 KB Output is correct
29 Correct 711 ms 3724 KB Output is correct
30 Correct 409 ms 2452 KB Output is correct
31 Correct 510 ms 2408 KB Output is correct
32 Correct 810 ms 4868 KB Output is correct
33 Correct 74 ms 1076 KB Output is correct
34 Correct 40 ms 1044 KB Output is correct
35 Correct 90 ms 1076 KB Output is correct
36 Correct 60 ms 988 KB Output is correct
37 Correct 771 ms 4984 KB Output is correct
38 Correct 738 ms 4000 KB Output is correct
39 Correct 758 ms 4744 KB Output is correct
40 Correct 811 ms 5732 KB Output is correct
41 Correct 771 ms 5496 KB Output is correct
42 Runtime error 498 ms 6028 KB Execution killed with signal 6
43 Halted 0 ms 0 KB -