oj.uz

답안 #682664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682664 2023-01-16T17:36:43 Z phoenix Segments (IZhO18_segments) C++17
22 / 100
 5000 ms 6580 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].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();
        }
    }
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 17 ms 544 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 15 ms 488 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 17 ms 564 KB Output is correct
11 Correct 16 ms 544 KB Output is correct
12 Correct 12 ms 484 KB Output is correct
13 Correct 17 ms 596 KB Output is correct
14 Correct 21 ms 480 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 452 KB Output is correct
18 Correct 19 ms 588 KB Output is correct
19 Correct 14 ms 540 KB Output is correct
20 Correct 13 ms 456 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 734 ms 3828 KB Output is correct
2 Correct 751 ms 3832 KB Output is correct
3 Correct 751 ms 3936 KB Output is correct
4 Correct 763 ms 4020 KB Output is correct
5 Correct 820 ms 6580 KB Output is correct
6 Correct 867 ms 6560 KB Output is correct
7 Correct 774 ms 3732 KB Output is correct
8 Correct 734 ms 3708 KB Output is correct
9 Correct 750 ms 3972 KB Output is correct
10 Correct 443 ms 2084 KB Output is correct
11 Correct 532 ms 2444 KB Output is correct
12 Correct 875 ms 5568 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 1044 KB Output is correct
2 Correct 51 ms 984 KB Output is correct
3 Correct 107 ms 1124 KB Output is correct
4 Correct 43 ms 984 KB Output is correct
5 Correct 854 ms 5428 KB Output is correct
6 Correct 850 ms 4588 KB Output is correct
7 Correct 848 ms 5152 KB Output is correct
8 Correct 836 ms 6532 KB Output is correct
9 Correct 799 ms 6304 KB Output is correct
10 Execution timed out 5048 ms 5636 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 1044 KB Output is correct
2 Correct 48 ms 1020 KB Output is correct
3 Correct 47 ms 1052 KB Output is correct
4 Correct 53 ms 964 KB Output is correct
5 Correct 851 ms 5652 KB Output is correct
6 Correct 341 ms 1688 KB Output is correct
7 Correct 827 ms 5940 KB Output is correct
8 Correct 454 ms 2128 KB Output is correct
9 Execution timed out 5039 ms 3008 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 17 ms 544 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 15 ms 488 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 17 ms 564 KB Output is correct
11 Correct 16 ms 544 KB Output is correct
12 Correct 12 ms 484 KB Output is correct
13 Correct 17 ms 596 KB Output is correct
14 Correct 21 ms 480 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 452 KB Output is correct
18 Correct 19 ms 588 KB Output is correct
19 Correct 14 ms 540 KB Output is correct
20 Correct 13 ms 456 KB Output is correct
21 Correct 734 ms 3828 KB Output is correct
22 Correct 751 ms 3832 KB Output is correct
23 Correct 751 ms 3936 KB Output is correct
24 Correct 763 ms 4020 KB Output is correct
25 Correct 820 ms 6580 KB Output is correct
26 Correct 867 ms 6560 KB Output is correct
27 Correct 774 ms 3732 KB Output is correct
28 Correct 734 ms 3708 KB Output is correct
29 Correct 750 ms 3972 KB Output is correct
30 Correct 443 ms 2084 KB Output is correct
31 Correct 532 ms 2444 KB Output is correct
32 Correct 875 ms 5568 KB Output is correct
33 Correct 54 ms 1044 KB Output is correct
34 Correct 48 ms 1020 KB Output is correct
35 Correct 47 ms 1052 KB Output is correct
36 Correct 53 ms 964 KB Output is correct
37 Correct 851 ms 5652 KB Output is correct
38 Correct 341 ms 1688 KB Output is correct
39 Correct 827 ms 5940 KB Output is correct
40 Correct 454 ms 2128 KB Output is correct
41 Execution timed out 5039 ms 3008 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 17 ms 544 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 15 ms 488 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 17 ms 564 KB Output is correct
11 Correct 16 ms 544 KB Output is correct
12 Correct 12 ms 484 KB Output is correct
13 Correct 17 ms 596 KB Output is correct
14 Correct 21 ms 480 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 452 KB Output is correct
18 Correct 19 ms 588 KB Output is correct
19 Correct 14 ms 540 KB Output is correct
20 Correct 13 ms 456 KB Output is correct
21 Correct 734 ms 3828 KB Output is correct
22 Correct 751 ms 3832 KB Output is correct
23 Correct 751 ms 3936 KB Output is correct
24 Correct 763 ms 4020 KB Output is correct
25 Correct 820 ms 6580 KB Output is correct
26 Correct 867 ms 6560 KB Output is correct
27 Correct 774 ms 3732 KB Output is correct
28 Correct 734 ms 3708 KB Output is correct
29 Correct 750 ms 3972 KB Output is correct
30 Correct 443 ms 2084 KB Output is correct
31 Correct 532 ms 2444 KB Output is correct
32 Correct 875 ms 5568 KB Output is correct
33 Correct 58 ms 1044 KB Output is correct
34 Correct 51 ms 984 KB Output is correct
35 Correct 107 ms 1124 KB Output is correct
36 Correct 43 ms 984 KB Output is correct
37 Correct 854 ms 5428 KB Output is correct
38 Correct 850 ms 4588 KB Output is correct
39 Correct 848 ms 5152 KB Output is correct
40 Correct 836 ms 6532 KB Output is correct
41 Correct 799 ms 6304 KB Output is correct
42 Execution timed out 5048 ms 5636 KB Time limit exceeded
43 Halted 0 ms 0 KB -