oj.uz

Submission #174434

# Submission time Handle Problem Language Result Execution time Memory
174434 2020-01-06T11:30:42 Z mcdx9524 Segments (IZhO18_segments) C++14
75 / 100
 5000 ms 6336 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return uniform_int_distribution <int> (l, r) (rnd);
}

const int N = 5e3 + 7;

int t, a, b, l, r, k;
int cur_id, id;

struct ev {
    int l, r, id;
};

int inter(int &l, int &r, int &a, int &b) {
    return max(0, min(r, b) - max(l, a) + 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, tp;
    cin >> n >> tp;
    int last_ans = 0;
    vector <ev> seg;
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (t == 1) {
            cin >> a >> b;
            l = a ^ (tp * last_ans);
            r = b ^ (tp * last_ans);
            if (l > r) {
                swap(l, r);
            }
            cur_id++;
            seg.push_back({l, r, cur_id});
        } else if (t == 2) {
            cin >> id;
            for (int j = 0; j < (int) seg.size(); j++) {
                if (seg[j].id == id) {
                    seg.erase(seg.begin() + j);
                    break;
                }
            }
        } else {
            cin >> a >> b >> k;
            l = a ^ (tp * last_ans);
            r = b ^ (tp * last_ans);
            if (l > r) {
                swap(l, r);
            }
            last_ans = 0;
            for (int j = 0; j < (int) seg.size(); j++) {
                if (inter(seg[j].l, seg[j].r, l, r) >= k) {
                    last_ans++;
                }
            }
            cout << last_ans << '\n';
        }
    }
    return 0;
}

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 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 12 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 9 ms 380 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 16 ms 376 KB Output is correct
12 Correct 17 ms 376 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 9 ms 376 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 4 ms 376 KB Output is correct
17 Correct 8 ms 376 KB Output is correct
18 Correct 7 ms 380 KB Output is correct
19 Correct 8 ms 380 KB Output is correct
20 Correct 8 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4905 ms 1436 KB Output is correct
2 Correct 4906 ms 1520 KB Output is correct
3 Correct 4904 ms 1436 KB Output is correct
4 Correct 4861 ms 1564 KB Output is correct
5 Correct 1080 ms 2032 KB Output is correct
6 Correct 570 ms 2160 KB Output is correct
7 Correct 4901 ms 1480 KB Output is correct
8 Correct 4905 ms 1492 KB Output is correct
9 Correct 4885 ms 1416 KB Output is correct
10 Correct 3093 ms 1192 KB Output is correct
11 Correct 3980 ms 1252 KB Output is correct
12 Correct 4099 ms 2032 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 504 KB Output is correct
2 Correct 43 ms 2296 KB Output is correct
3 Correct 68 ms 2296 KB Output is correct
4 Correct 44 ms 2472 KB Output is correct
5 Correct 3990 ms 3936 KB Output is correct
6 Correct 4704 ms 3944 KB Output is correct
7 Correct 4439 ms 3916 KB Output is correct
8 Correct 1037 ms 3816 KB Output is correct
9 Correct 812 ms 3944 KB Output is correct
10 Correct 2005 ms 3624 KB Output is correct
11 Correct 328 ms 2424 KB Output is correct
12 Correct 1971 ms 3696 KB Output is correct
13 Correct 2149 ms 3464 KB Output is correct
14 Correct 1779 ms 3040 KB Output is correct
15 Correct 1585 ms 3100 KB Output is correct
16 Correct 1152 ms 2828 KB Output is correct
17 Correct 4901 ms 3964 KB Output is correct
18 Correct 4890 ms 4004 KB Output is correct
19 Correct 4945 ms 3780 KB Output is correct
20 Correct 4938 ms 3868 KB Output is correct
21 Correct 460 ms 2552 KB Output is correct
22 Correct 2025 ms 2980 KB Output is correct
23 Correct 2175 ms 3328 KB Output is correct
24 Correct 2086 ms 3216 KB Output is correct
25 Correct 55 ms 2296 KB Output is correct
26 Correct 46 ms 2296 KB Output is correct
27 Correct 53 ms 2408 KB Output is correct
28 Correct 48 ms 2424 KB Output is correct
29 Correct 2183 ms 3336 KB Output is correct
30 Correct 2179 ms 3448 KB Output is correct
31 Correct 744 ms 3944 KB Output is correct
32 Correct 2012 ms 3692 KB Output is correct
33 Correct 2105 ms 3380 KB Output is correct
34 Correct 1564 ms 2964 KB Output is correct
35 Correct 2213 ms 3448 KB Output is correct
36 Correct 2045 ms 3440 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 376 KB Output is correct
2 Correct 46 ms 2552 KB Output is correct
3 Correct 46 ms 2492 KB Output is correct
4 Correct 50 ms 2652 KB Output is correct
5 Correct 3473 ms 4092 KB Output is correct
6 Correct 2366 ms 4396 KB Output is correct
7 Correct 2746 ms 4176 KB Output is correct
8 Correct 3233 ms 4208 KB Output is correct
9 Correct 1975 ms 3400 KB Output is correct
10 Correct 1854 ms 3916 KB Output is correct
11 Correct 977 ms 3000 KB Output is correct
12 Correct 440 ms 3944 KB Output is correct
13 Correct 2184 ms 3708 KB Output is correct
14 Correct 1872 ms 3300 KB Output is correct
15 Correct 885 ms 3816 KB Output is correct
16 Correct 2118 ms 3628 KB Output is correct
17 Correct 4910 ms 4168 KB Output is correct
18 Correct 4921 ms 4420 KB Output is correct
19 Correct 4900 ms 4392 KB Output is correct
20 Correct 4889 ms 4244 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 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 12 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 9 ms 380 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 16 ms 376 KB Output is correct
12 Correct 17 ms 376 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 9 ms 376 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 4 ms 376 KB Output is correct
17 Correct 8 ms 376 KB Output is correct
18 Correct 7 ms 380 KB Output is correct
19 Correct 8 ms 380 KB Output is correct
20 Correct 8 ms 376 KB Output is correct
21 Correct 4905 ms 1436 KB Output is correct
22 Correct 4906 ms 1520 KB Output is correct
23 Correct 4904 ms 1436 KB Output is correct
24 Correct 4861 ms 1564 KB Output is correct
25 Correct 1080 ms 2032 KB Output is correct
26 Correct 570 ms 2160 KB Output is correct
27 Correct 4901 ms 1480 KB Output is correct
28 Correct 4905 ms 1492 KB Output is correct
29 Correct 4885 ms 1416 KB Output is correct
30 Correct 3093 ms 1192 KB Output is correct
31 Correct 3980 ms 1252 KB Output is correct
32 Correct 4099 ms 2032 KB Output is correct
33 Correct 44 ms 376 KB Output is correct
34 Correct 46 ms 2552 KB Output is correct
35 Correct 46 ms 2492 KB Output is correct
36 Correct 50 ms 2652 KB Output is correct
37 Correct 3473 ms 4092 KB Output is correct
38 Correct 2366 ms 4396 KB Output is correct
39 Correct 2746 ms 4176 KB Output is correct
40 Correct 3233 ms 4208 KB Output is correct
41 Correct 1975 ms 3400 KB Output is correct
42 Correct 1854 ms 3916 KB Output is correct
43 Correct 977 ms 3000 KB Output is correct
44 Correct 440 ms 3944 KB Output is correct
45 Correct 2184 ms 3708 KB Output is correct
46 Correct 1872 ms 3300 KB Output is correct
47 Correct 885 ms 3816 KB Output is correct
48 Correct 2118 ms 3628 KB Output is correct
49 Correct 4910 ms 4168 KB Output is correct
50 Correct 4921 ms 4420 KB Output is correct
51 Correct 4900 ms 4392 KB Output is correct
52 Correct 4889 ms 4244 KB Output is correct
53 Correct 50 ms 2552 KB Output is correct
54 Correct 52 ms 2552 KB Output is correct
55 Correct 48 ms 2552 KB Output is correct
56 Correct 46 ms 2552 KB Output is correct
57 Correct 4269 ms 4212 KB Output is correct
58 Correct 1659 ms 4408 KB Output is correct
59 Correct 4672 ms 4380 KB Output is correct
60 Correct 1399 ms 4320 KB Output is correct
61 Correct 2150 ms 3592 KB Output is correct
62 Correct 1100 ms 3916 KB Output is correct
63 Correct 628 ms 3840 KB Output is correct
64 Correct 1041 ms 3808 KB Output is correct
65 Correct 1305 ms 3048 KB Output is correct
66 Correct 1093 ms 3092 KB Output is correct
67 Correct 2062 ms 3868 KB Output is correct
68 Correct 2197 ms 3320 KB Output is correct
69 Correct 4906 ms 4196 KB Output is correct
70 Correct 4902 ms 4388 KB Output is correct
71 Correct 4902 ms 4156 KB Output is correct
72 Correct 4917 ms 4120 KB Output is correct
73 Correct 1532 ms 2940 KB Output is correct
74 Correct 2189 ms 3464 KB Output is correct
75 Correct 214 ms 3908 KB Output is correct
76 Correct 587 ms 3944 KB Output is correct
77 Correct 48 ms 2552 KB Output is correct
78 Correct 46 ms 2552 KB Output is correct
79 Correct 52 ms 2552 KB Output is correct
80 Correct 47 ms 2460 KB Output is correct
81 Correct 2174 ms 3420 KB Output is correct
82 Correct 1533 ms 3052 KB Output is correct
83 Correct 887 ms 2916 KB Output is correct
84 Correct 2187 ms 3608 KB Output is correct
85 Correct 2051 ms 3468 KB Output is correct
86 Correct 1997 ms 3816 KB Output is correct
87 Correct 1986 ms 3324 KB Output is correct
88 Correct 937 ms 3016 KB Output is correct

Subtask #6
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 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 12 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 9 ms 380 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 16 ms 376 KB Output is correct
12 Correct 17 ms 376 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 9 ms 376 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 4 ms 376 KB Output is correct
17 Correct 8 ms 376 KB Output is correct
18 Correct 7 ms 380 KB Output is correct
19 Correct 8 ms 380 KB Output is correct
20 Correct 8 ms 376 KB Output is correct
21 Correct 4905 ms 1436 KB Output is correct
22 Correct 4906 ms 1520 KB Output is correct
23 Correct 4904 ms 1436 KB Output is correct
24 Correct 4861 ms 1564 KB Output is correct
25 Correct 1080 ms 2032 KB Output is correct
26 Correct 570 ms 2160 KB Output is correct
27 Correct 4901 ms 1480 KB Output is correct
28 Correct 4905 ms 1492 KB Output is correct
29 Correct 4885 ms 1416 KB Output is correct
30 Correct 3093 ms 1192 KB Output is correct
31 Correct 3980 ms 1252 KB Output is correct
32 Correct 4099 ms 2032 KB Output is correct
33 Correct 51 ms 504 KB Output is correct
34 Correct 43 ms 2296 KB Output is correct
35 Correct 68 ms 2296 KB Output is correct
36 Correct 44 ms 2472 KB Output is correct
37 Correct 3990 ms 3936 KB Output is correct
38 Correct 4704 ms 3944 KB Output is correct
39 Correct 4439 ms 3916 KB Output is correct
40 Correct 1037 ms 3816 KB Output is correct
41 Correct 812 ms 3944 KB Output is correct
42 Correct 2005 ms 3624 KB Output is correct
43 Correct 328 ms 2424 KB Output is correct
44 Correct 1971 ms 3696 KB Output is correct
45 Correct 2149 ms 3464 KB Output is correct
46 Correct 1779 ms 3040 KB Output is correct
47 Correct 1585 ms 3100 KB Output is correct
48 Correct 1152 ms 2828 KB Output is correct
49 Correct 4901 ms 3964 KB Output is correct
50 Correct 4890 ms 4004 KB Output is correct
51 Correct 4945 ms 3780 KB Output is correct
52 Correct 4938 ms 3868 KB Output is correct
53 Correct 460 ms 2552 KB Output is correct
54 Correct 2025 ms 2980 KB Output is correct
55 Correct 2175 ms 3328 KB Output is correct
56 Correct 2086 ms 3216 KB Output is correct
57 Correct 55 ms 2296 KB Output is correct
58 Correct 46 ms 2296 KB Output is correct
59 Correct 53 ms 2408 KB Output is correct
60 Correct 48 ms 2424 KB Output is correct
61 Correct 2183 ms 3336 KB Output is correct
62 Correct 2179 ms 3448 KB Output is correct
63 Correct 744 ms 3944 KB Output is correct
64 Correct 2012 ms 3692 KB Output is correct
65 Correct 2105 ms 3380 KB Output is correct
66 Correct 1564 ms 2964 KB Output is correct
67 Correct 2213 ms 3448 KB Output is correct
68 Correct 2045 ms 3440 KB Output is correct
69 Correct 44 ms 376 KB Output is correct
70 Correct 46 ms 2552 KB Output is correct
71 Correct 46 ms 2492 KB Output is correct
72 Correct 50 ms 2652 KB Output is correct
73 Correct 3473 ms 4092 KB Output is correct
74 Correct 2366 ms 4396 KB Output is correct
75 Correct 2746 ms 4176 KB Output is correct
76 Correct 3233 ms 4208 KB Output is correct
77 Correct 1975 ms 3400 KB Output is correct
78 Correct 1854 ms 3916 KB Output is correct
79 Correct 977 ms 3000 KB Output is correct
80 Correct 440 ms 3944 KB Output is correct
81 Correct 2184 ms 3708 KB Output is correct
82 Correct 1872 ms 3300 KB Output is correct
83 Correct 885 ms 3816 KB Output is correct
84 Correct 2118 ms 3628 KB Output is correct
85 Correct 4910 ms 4168 KB Output is correct
86 Correct 4921 ms 4420 KB Output is correct
87 Correct 4900 ms 4392 KB Output is correct
88 Correct 4889 ms 4244 KB Output is correct
89 Correct 50 ms 2552 KB Output is correct
90 Correct 52 ms 2552 KB Output is correct
91 Correct 48 ms 2552 KB Output is correct
92 Correct 46 ms 2552 KB Output is correct
93 Correct 4269 ms 4212 KB Output is correct
94 Correct 1659 ms 4408 KB Output is correct
95 Correct 4672 ms 4380 KB Output is correct
96 Correct 1399 ms 4320 KB Output is correct
97 Correct 2150 ms 3592 KB Output is correct
98 Correct 1100 ms 3916 KB Output is correct
99 Correct 628 ms 3840 KB Output is correct
100 Correct 1041 ms 3808 KB Output is correct
101 Correct 1305 ms 3048 KB Output is correct
102 Correct 1093 ms 3092 KB Output is correct
103 Correct 2062 ms 3868 KB Output is correct
104 Correct 2197 ms 3320 KB Output is correct
105 Correct 4906 ms 4196 KB Output is correct
106 Correct 4902 ms 4388 KB Output is correct
107 Correct 4902 ms 4156 KB Output is correct
108 Correct 4917 ms 4120 KB Output is correct
109 Correct 1532 ms 2940 KB Output is correct
110 Correct 2189 ms 3464 KB Output is correct
111 Correct 214 ms 3908 KB Output is correct
112 Correct 587 ms 3944 KB Output is correct
113 Correct 48 ms 2552 KB Output is correct
114 Correct 46 ms 2552 KB Output is correct
115 Correct 52 ms 2552 KB Output is correct
116 Correct 47 ms 2460 KB Output is correct
117 Correct 2174 ms 3420 KB Output is correct
118 Correct 1533 ms 3052 KB Output is correct
119 Correct 887 ms 2916 KB Output is correct
120 Correct 2187 ms 3608 KB Output is correct
121 Correct 2051 ms 3468 KB Output is correct
122 Correct 1997 ms 3816 KB Output is correct
123 Correct 1986 ms 3324 KB Output is correct
124 Correct 937 ms 3016 KB Output is correct
125 Correct 99 ms 4700 KB Output is correct
126 Correct 102 ms 4708 KB Output is correct
127 Correct 126 ms 4728 KB Output is correct
128 Correct 108 ms 4728 KB Output is correct
129 Correct 94 ms 4728 KB Output is correct
130 Correct 112 ms 4728 KB Output is correct
131 Execution timed out 5085 ms 6336 KB Time limit exceeded
132 Halted 0 ms 0 KB -