oj.uz

Submission #93893

# Submission time Handle Problem Language Result Execution time Memory
93893 2019-01-12T21:09:41 Z dalgerok Segments (IZhO18_segments) C++14
100 / 100
 4540 ms 9608 KB 
#include<bits/stdc++.h>
using namespace std;



const int N = 2e5 + 5, S = 1000, M = N / S + 5;



int n, t, ans;
int sz, alive, L[N], R[N];
pair < int, int > a[N];
int add[S], sz_add, del[S], sz_del;
bool killed[N];
int sz_l[S], sz_r[S];
int b_l[S][S], b_r[S][S];
int m;

inline void rebuild(){
    m = 0;
    for(int i = 1; i <= sz; i++){
        if(killed[i] == false){
            a[m++] = make_pair(R[i] - L[i] + 1, i);
        }
    }
    sort(a, a + m);
    sz_add = sz_del = 0;
    for(int i = 0; i <= m / S; i++){
        sz_l[i] = sz_r[i] = 0;
    }
    for(int i = 0; i < m; i++){
        b_l[i / S][sz_l[i / S]++] = L[a[i].second];
        b_r[i / S][sz_r[i / S]++] = R[a[i].second];
    }
    for(int i = 0; i <= m / S; i++){
        sort(b_l[i], b_l[i] + sz_l[i]);
        sort(b_r[i], b_r[i] + sz_r[i]);
    }
}

inline int intersect(int l1, int r1, int l2, int r2){
    return max(0, min(r1, r2) - max(l1, l2) + 1);
}


/// number of L > x from l to r
inline int calcL(int l, int r, int x){
    int res = 0;
    int bl = l / S, br = r / S;
    if(bl == br){
        for(int i = l; i <= r; i++){
            res += (L[a[i].second] > x);
        }
        return res;
    }
    for(int i = bl + 1; i <= br - 1; i++){
        int j = lower_bound(b_l[i], b_l[i] + sz_l[i], x + 1) - b_l[i];
        res += S - j;
    }
    for(int i = l; i < (bl + 1) * S; i++){
        res += (L[a[i].second] > x);
    }
    for(int i = br * S; i <= r; i++){
        res += (L[a[i].second] > x);
    }
    return res;
}
/// number of R < x from l to r
inline int calcR(int l, int r, int x){
    int res = 0;
    int bl = l / S, br = r / S;
    if(bl == br){
        for(int i = l; i <= r; i++){
            res += (R[a[i].second] < x);
        }
        return res;
    }
    for(int i = bl + 1; i <= br - 1; i++){
        int j = lower_bound(b_r[i], b_r[i] + sz_r[i], x) - b_r[i];
        res += j;
    }
    for(int i = l; i < (bl + 1) * S; i++){
        res += (R[a[i].second] < x);
    }
    for(int i = br * S; i <= r; i++){
        res += (R[a[i].second] < x);
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> t;
    for(int i = 1; i <= n; i++){
        if(i % S == 0){
            rebuild();
        }
        int type;
        cin >> type;
        if(type == 1){
            int l, r;
            cin >> l >> r;
            l ^= (1LL * t * ans);
            r ^= (1LL * t * ans);
            if(l > r){
                swap(l, r);
            }
            sz += 1;
            L[sz] = l;
            R[sz] = r;
            add[sz_add++] = sz;
            alive += 1;
        }
        else if(type == 2){
            int x;
            cin >> x;
            del[sz_del++] = x;
            killed[x] = true;
            alive -= 1;
        }
        else{
            int l, r, k;
            cin >> l >> r >> k;
            l ^= (1LL * t * ans);
            r ^= (1LL * t * ans);
            if(l > r){
                swap(l, r);
            }
            if(r - l + 1 < k){
                ans = 0;
                cout << "0\n";
                continue;
            }
            int res = 0;
            for(int j = 0; j < sz_add; j++){
                res += (intersect(l, r, L[add[j]], R[add[j]]) < k);
            }
            for(int j = 0; j < sz_del; j++){
                res -= (intersect(l, r, L[del[j]], R[del[j]]) < k);
            }
            int pos = lower_bound(a, a + m, make_pair(k, 0)) - a;
            res += pos;
            res += calcL(pos, m - 1, r - k + 1);
            res += calcR(pos, m - 1, l + k - 1);
            ans = alive - res;
            cout << ans << "\n";
        }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 9 ms 648 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 7 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 11 ms 632 KB Output is correct
12 Correct 11 ms 632 KB Output is correct
13 Correct 7 ms 632 KB Output is correct
14 Correct 7 ms 504 KB Output is correct
15 Correct 5 ms 504 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 7 ms 504 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 8 ms 504 KB Output is correct
20 Correct 8 ms 504 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1198 ms 2572 KB Output is correct
2 Correct 1229 ms 2808 KB Output is correct
3 Correct 1174 ms 2808 KB Output is correct
4 Correct 1185 ms 2800 KB Output is correct
5 Correct 931 ms 3444 KB Output is correct
6 Correct 908 ms 3608 KB Output is correct
7 Correct 1206 ms 2816 KB Output is correct
8 Correct 1170 ms 2668 KB Output is correct
9 Correct 1181 ms 2808 KB Output is correct
10 Correct 735 ms 2020 KB Output is correct
11 Correct 773 ms 2208 KB Output is correct
12 Correct 1081 ms 3064 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1272 KB Output is correct
2 Correct 57 ms 1528 KB Output is correct
3 Correct 89 ms 1524 KB Output is correct
4 Correct 60 ms 1604 KB Output is correct
5 Correct 1232 ms 2968 KB Output is correct
6 Correct 1276 ms 2936 KB Output is correct
7 Correct 1256 ms 2968 KB Output is correct
8 Correct 957 ms 3584 KB Output is correct
9 Correct 908 ms 3576 KB Output is correct
10 Correct 917 ms 3064 KB Output is correct
11 Correct 250 ms 1668 KB Output is correct
12 Correct 941 ms 3064 KB Output is correct
13 Correct 870 ms 2832 KB Output is correct
14 Correct 628 ms 2168 KB Output is correct
15 Correct 600 ms 2168 KB Output is correct
16 Correct 510 ms 1980 KB Output is correct
17 Correct 1355 ms 2788 KB Output is correct
18 Correct 1354 ms 2808 KB Output is correct
19 Correct 1367 ms 2668 KB Output is correct
20 Correct 1378 ms 2740 KB Output is correct
21 Correct 272 ms 2032 KB Output is correct
22 Correct 780 ms 2508 KB Output is correct
23 Correct 828 ms 2792 KB Output is correct
24 Correct 784 ms 2668 KB Output is correct
25 Correct 71 ms 1784 KB Output is correct
26 Correct 61 ms 1784 KB Output is correct
27 Correct 70 ms 1784 KB Output is correct
28 Correct 63 ms 1784 KB Output is correct
29 Correct 855 ms 2948 KB Output is correct
30 Correct 871 ms 2976 KB Output is correct
31 Correct 917 ms 3688 KB Output is correct
32 Correct 917 ms 3228 KB Output is correct
33 Correct 882 ms 3072 KB Output is correct
34 Correct 538 ms 2440 KB Output is correct
35 Correct 805 ms 2936 KB Output is correct
36 Correct 938 ms 3192 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1528 KB Output is correct
2 Correct 60 ms 1716 KB Output is correct
3 Correct 61 ms 1728 KB Output is correct
4 Correct 64 ms 1780 KB Output is correct
5 Correct 1121 ms 3424 KB Output is correct
6 Correct 628 ms 2168 KB Output is correct
7 Correct 1032 ms 3448 KB Output is correct
8 Correct 809 ms 2292 KB Output is correct
9 Correct 653 ms 2540 KB Output is correct
10 Correct 915 ms 3248 KB Output is correct
11 Correct 379 ms 2176 KB Output is correct
12 Correct 879 ms 3868 KB Output is correct
13 Correct 829 ms 3116 KB Output is correct
14 Correct 634 ms 2424 KB Output is correct
15 Correct 899 ms 3648 KB Output is correct
16 Correct 893 ms 3012 KB Output is correct
17 Correct 1157 ms 2920 KB Output is correct
18 Correct 1154 ms 2952 KB Output is correct
19 Correct 1184 ms 2828 KB Output is correct
20 Correct 1195 ms 2772 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 9 ms 648 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 7 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 11 ms 632 KB Output is correct
12 Correct 11 ms 632 KB Output is correct
13 Correct 7 ms 632 KB Output is correct
14 Correct 7 ms 504 KB Output is correct
15 Correct 5 ms 504 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 7 ms 504 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 8 ms 504 KB Output is correct
20 Correct 8 ms 504 KB Output is correct
21 Correct 1198 ms 2572 KB Output is correct
22 Correct 1229 ms 2808 KB Output is correct
23 Correct 1174 ms 2808 KB Output is correct
24 Correct 1185 ms 2800 KB Output is correct
25 Correct 931 ms 3444 KB Output is correct
26 Correct 908 ms 3608 KB Output is correct
27 Correct 1206 ms 2816 KB Output is correct
28 Correct 1170 ms 2668 KB Output is correct
29 Correct 1181 ms 2808 KB Output is correct
30 Correct 735 ms 2020 KB Output is correct
31 Correct 773 ms 2208 KB Output is correct
32 Correct 1081 ms 3064 KB Output is correct
33 Correct 60 ms 1528 KB Output is correct
34 Correct 60 ms 1716 KB Output is correct
35 Correct 61 ms 1728 KB Output is correct
36 Correct 64 ms 1780 KB Output is correct
37 Correct 1121 ms 3424 KB Output is correct
38 Correct 628 ms 2168 KB Output is correct
39 Correct 1032 ms 3448 KB Output is correct
40 Correct 809 ms 2292 KB Output is correct
41 Correct 653 ms 2540 KB Output is correct
42 Correct 915 ms 3248 KB Output is correct
43 Correct 379 ms 2176 KB Output is correct
44 Correct 879 ms 3868 KB Output is correct
45 Correct 829 ms 3116 KB Output is correct
46 Correct 634 ms 2424 KB Output is correct
47 Correct 899 ms 3648 KB Output is correct
48 Correct 893 ms 3012 KB Output is correct
49 Correct 1157 ms 2920 KB Output is correct
50 Correct 1154 ms 2952 KB Output is correct
51 Correct 1184 ms 2828 KB Output is correct
52 Correct 1195 ms 2772 KB Output is correct
53 Correct 64 ms 1728 KB Output is correct
54 Correct 65 ms 1772 KB Output is correct
55 Correct 60 ms 1656 KB Output is correct
56 Correct 61 ms 1784 KB Output is correct
57 Correct 1054 ms 2640 KB Output is correct
58 Correct 383 ms 2040 KB Output is correct
59 Correct 1075 ms 3132 KB Output is correct
60 Correct 414 ms 2520 KB Output is correct
61 Correct 851 ms 3640 KB Output is correct
62 Correct 918 ms 4056 KB Output is correct
63 Correct 884 ms 4200 KB Output is correct
64 Correct 923 ms 4036 KB Output is correct
65 Correct 455 ms 2728 KB Output is correct
66 Correct 420 ms 2660 KB Output is correct
67 Correct 908 ms 3648 KB Output is correct
68 Correct 802 ms 3336 KB Output is correct
69 Correct 1169 ms 3552 KB Output is correct
70 Correct 1167 ms 3388 KB Output is correct
71 Correct 1215 ms 3308 KB Output is correct
72 Correct 1172 ms 3456 KB Output is correct
73 Correct 567 ms 2832 KB Output is correct
74 Correct 800 ms 3452 KB Output is correct
75 Correct 859 ms 4376 KB Output is correct
76 Correct 876 ms 4284 KB Output is correct
77 Correct 64 ms 2296 KB Output is correct
78 Correct 61 ms 2268 KB Output is correct
79 Correct 65 ms 2296 KB Output is correct
80 Correct 61 ms 2296 KB Output is correct
81 Correct 743 ms 3296 KB Output is correct
82 Correct 563 ms 2756 KB Output is correct
83 Correct 368 ms 2500 KB Output is correct
84 Correct 762 ms 3276 KB Output is correct
85 Correct 870 ms 3764 KB Output is correct
86 Correct 898 ms 3704 KB Output is correct
87 Correct 684 ms 3248 KB Output is correct
88 Correct 359 ms 2552 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 9 ms 648 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 7 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 11 ms 632 KB Output is correct
12 Correct 11 ms 632 KB Output is correct
13 Correct 7 ms 632 KB Output is correct
14 Correct 7 ms 504 KB Output is correct
15 Correct 5 ms 504 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 7 ms 504 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 8 ms 504 KB Output is correct
20 Correct 8 ms 504 KB Output is correct
21 Correct 1198 ms 2572 KB Output is correct
22 Correct 1229 ms 2808 KB Output is correct
23 Correct 1174 ms 2808 KB Output is correct
24 Correct 1185 ms 2800 KB Output is correct
25 Correct 931 ms 3444 KB Output is correct
26 Correct 908 ms 3608 KB Output is correct
27 Correct 1206 ms 2816 KB Output is correct
28 Correct 1170 ms 2668 KB Output is correct
29 Correct 1181 ms 2808 KB Output is correct
30 Correct 735 ms 2020 KB Output is correct
31 Correct 773 ms 2208 KB Output is correct
32 Correct 1081 ms 3064 KB Output is correct
33 Correct 67 ms 1272 KB Output is correct
34 Correct 57 ms 1528 KB Output is correct
35 Correct 89 ms 1524 KB Output is correct
36 Correct 60 ms 1604 KB Output is correct
37 Correct 1232 ms 2968 KB Output is correct
38 Correct 1276 ms 2936 KB Output is correct
39 Correct 1256 ms 2968 KB Output is correct
40 Correct 957 ms 3584 KB Output is correct
41 Correct 908 ms 3576 KB Output is correct
42 Correct 917 ms 3064 KB Output is correct
43 Correct 250 ms 1668 KB Output is correct
44 Correct 941 ms 3064 KB Output is correct
45 Correct 870 ms 2832 KB Output is correct
46 Correct 628 ms 2168 KB Output is correct
47 Correct 600 ms 2168 KB Output is correct
48 Correct 510 ms 1980 KB Output is correct
49 Correct 1355 ms 2788 KB Output is correct
50 Correct 1354 ms 2808 KB Output is correct
51 Correct 1367 ms 2668 KB Output is correct
52 Correct 1378 ms 2740 KB Output is correct
53 Correct 272 ms 2032 KB Output is correct
54 Correct 780 ms 2508 KB Output is correct
55 Correct 828 ms 2792 KB Output is correct
56 Correct 784 ms 2668 KB Output is correct
57 Correct 71 ms 1784 KB Output is correct
58 Correct 61 ms 1784 KB Output is correct
59 Correct 70 ms 1784 KB Output is correct
60 Correct 63 ms 1784 KB Output is correct
61 Correct 855 ms 2948 KB Output is correct
62 Correct 871 ms 2976 KB Output is correct
63 Correct 917 ms 3688 KB Output is correct
64 Correct 917 ms 3228 KB Output is correct
65 Correct 882 ms 3072 KB Output is correct
66 Correct 538 ms 2440 KB Output is correct
67 Correct 805 ms 2936 KB Output is correct
68 Correct 938 ms 3192 KB Output is correct
69 Correct 60 ms 1528 KB Output is correct
70 Correct 60 ms 1716 KB Output is correct
71 Correct 61 ms 1728 KB Output is correct
72 Correct 64 ms 1780 KB Output is correct
73 Correct 1121 ms 3424 KB Output is correct
74 Correct 628 ms 2168 KB Output is correct
75 Correct 1032 ms 3448 KB Output is correct
76 Correct 809 ms 2292 KB Output is correct
77 Correct 653 ms 2540 KB Output is correct
78 Correct 915 ms 3248 KB Output is correct
79 Correct 379 ms 2176 KB Output is correct
80 Correct 879 ms 3868 KB Output is correct
81 Correct 829 ms 3116 KB Output is correct
82 Correct 634 ms 2424 KB Output is correct
83 Correct 899 ms 3648 KB Output is correct
84 Correct 893 ms 3012 KB Output is correct
85 Correct 1157 ms 2920 KB Output is correct
86 Correct 1154 ms 2952 KB Output is correct
87 Correct 1184 ms 2828 KB Output is correct
88 Correct 1195 ms 2772 KB Output is correct
89 Correct 64 ms 1728 KB Output is correct
90 Correct 65 ms 1772 KB Output is correct
91 Correct 60 ms 1656 KB Output is correct
92 Correct 61 ms 1784 KB Output is correct
93 Correct 1054 ms 2640 KB Output is correct
94 Correct 383 ms 2040 KB Output is correct
95 Correct 1075 ms 3132 KB Output is correct
96 Correct 414 ms 2520 KB Output is correct
97 Correct 851 ms 3640 KB Output is correct
98 Correct 918 ms 4056 KB Output is correct
99 Correct 884 ms 4200 KB Output is correct
100 Correct 923 ms 4036 KB Output is correct
101 Correct 455 ms 2728 KB Output is correct
102 Correct 420 ms 2660 KB Output is correct
103 Correct 908 ms 3648 KB Output is correct
104 Correct 802 ms 3336 KB Output is correct
105 Correct 1169 ms 3552 KB Output is correct
106 Correct 1167 ms 3388 KB Output is correct
107 Correct 1215 ms 3308 KB Output is correct
108 Correct 1172 ms 3456 KB Output is correct
109 Correct 567 ms 2832 KB Output is correct
110 Correct 800 ms 3452 KB Output is correct
111 Correct 859 ms 4376 KB Output is correct
112 Correct 876 ms 4284 KB Output is correct
113 Correct 64 ms 2296 KB Output is correct
114 Correct 61 ms 2268 KB Output is correct
115 Correct 65 ms 2296 KB Output is correct
116 Correct 61 ms 2296 KB Output is correct
117 Correct 743 ms 3296 KB Output is correct
118 Correct 563 ms 2756 KB Output is correct
119 Correct 368 ms 2500 KB Output is correct
120 Correct 762 ms 3276 KB Output is correct
121 Correct 870 ms 3764 KB Output is correct
122 Correct 898 ms 3704 KB Output is correct
123 Correct 684 ms 3248 KB Output is correct
124 Correct 359 ms 2552 KB Output is correct
125 Correct 128 ms 2764 KB Output is correct
126 Correct 130 ms 2708 KB Output is correct
127 Correct 155 ms 2680 KB Output is correct
128 Correct 140 ms 2620 KB Output is correct
129 Correct 123 ms 2656 KB Output is correct
130 Correct 138 ms 2692 KB Output is correct
131 Correct 1861 ms 3084 KB Output is correct
132 Correct 4049 ms 4872 KB Output is correct
133 Correct 4253 ms 9152 KB Output is correct
134 Correct 2324 ms 8036 KB Output is correct
135 Correct 4540 ms 9332 KB Output is correct
136 Correct 630 ms 7596 KB Output is correct
137 Correct 3770 ms 9476 KB Output is correct
138 Correct 3313 ms 7828 KB Output is correct
139 Correct 3708 ms 8540 KB Output is correct
140 Correct 3834 ms 9044 KB Output is correct
141 Correct 3501 ms 8284 KB Output is correct
142 Correct 763 ms 5820 KB Output is correct
143 Correct 1656 ms 6308 KB Output is correct
144 Correct 562 ms 5608 KB Output is correct
145 Correct 3796 ms 9148 KB Output is correct
146 Correct 2436 ms 7092 KB Output is correct
147 Correct 1690 ms 6364 KB Output is correct
148 Correct 1559 ms 6296 KB Output is correct
149 Correct 4392 ms 9012 KB Output is correct
150 Correct 4346 ms 8852 KB Output is correct
151 Correct 4413 ms 8944 KB Output is correct
152 Correct 4340 ms 8848 KB Output is correct
153 Correct 4384 ms 8928 KB Output is correct
154 Correct 4324 ms 8856 KB Output is correct
155 Correct 1080 ms 5972 KB Output is correct
156 Correct 1752 ms 6432 KB Output is correct
157 Correct 3892 ms 9292 KB Output is correct
158 Correct 3908 ms 9460 KB Output is correct
159 Correct 3478 ms 8052 KB Output is correct
160 Correct 2448 ms 7220 KB Output is correct
161 Correct 152 ms 5368 KB Output is correct
162 Correct 140 ms 5364 KB Output is correct
163 Correct 142 ms 5416 KB Output is correct
164 Correct 235 ms 5580 KB Output is correct
165 Correct 155 ms 5344 KB Output is correct
166 Correct 139 ms 5372 KB Output is correct
167 Correct 4287 ms 9608 KB Output is correct
168 Correct 3613 ms 9556 KB Output is correct
169 Correct 3778 ms 9120 KB Output is correct
170 Correct 3893 ms 9128 KB Output is correct
171 Correct 3568 ms 8388 KB Output is correct
172 Correct 2271 ms 6944 KB Output is correct
173 Correct 3886 ms 9208 KB Output is correct
174 Correct 2434 ms 6948 KB Output is correct
175 Correct 3709 ms 8464 KB Output is correct
176 Correct 1555 ms 6284 KB Output is correct
177 Correct 3386 ms 8036 KB Output is correct
178 Correct 3065 ms 7744 KB Output is correct