# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
117994 |
2019-06-17T15:54:32 Z |
keko37 |
Tenis (COI19_tenis) |
C++14 |
|
426 ms |
9536 KB |
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, q, ofs = 1;
int p[4][MAXN], pos[4][MAXN], mx[MAXN], val[MAXN];
struct node {
int val, pos, prop;
node () {}
node (int _val, int _pos, int _prop) {
val = _val; pos = _pos; prop = _prop;
}
} t[MAXN*3];
void ispis () {
for (int i=0; i<2*ofs; i++) {
cout << "bla " << i << " " << t[i].val << " " << t[i].pos << " " << t[i].prop << endl;
}
}
void propagate (int x) {
if (t[x].prop == 0) return;
t[x].val += t[x].prop;
if (x < ofs) {
t[2*x].prop += t[x].prop;
t[2*x+1].prop += t[x].prop;
}
t[x].prop = 0;
}
node spoji (node a, node b) {
if (a.val <= b.val) return a; else return b;
}
void update (int x, int from, int to, int low, int high, int br) {
//cout << "update " << from << " " << to << " " << br << endl;
propagate(x);
if (from <= low && high <= to) {
t[x].prop += br;
propagate(x);
return;
}
if (to < low || high < from) return;
update(2*x, from, to, low, (low + high)/2, br);
update(2*x+1, from, to, (low + high)/2+1, high, br);
t[x] = spoji(t[2*x], t[2*x+1]);
}
node upit (int x, int from, int to, int low, int high) {
propagate(x);
if (from <= low && high <= to) return t[x];
if (to < low || high < from) return node(MAXN, n, 0);
return spoji(upit(2*x, from, to, low, (low + high)/2), upit(2*x+1, from, to, (low + high)/2+1, high));
}
void ubaci (int v, int x, int sign) {
if (x >= v) return;
update(1, x-1, v-2, 0, ofs-1, sign);
}
void build () {
while (ofs < n) ofs *= 2;
for (int i=0; i<ofs; i++) {
if (i < n) t[i + ofs] = node(0, i, 0); else t[i + ofs] = node(MAXN, n, 0);
}
for (int i=ofs-1; i>0; i--) {
t[i] = spoji(t[2*i], t[2*i+1]);
}
//ispis();
for (int i=1; i<=n; i++){
ubaci(val[i], i, 1);
}
}
void novi (int r, int s) {
int v = 0;
for (int i=1; i<=3; i++) {
v = max(v, mx[p[i][s]]);
}
if (v != val[s]) {
ubaci(val[s], s, -1);
val[s] = v;
ubaci(val[s], s, 1);
}
}
void promjeni (int r, int a, int b) {
//cout << "mijenjam " << r << " " << a << " " << b << endl;
int x = pos[r][a], y = pos[r][b];
p[r][x] = b; p[r][y] = a;
pos[r][a] = y; pos[r][b] = x;
mx[a] = mx[b] = 0;
for (int i=1; i<=3; i++) {
mx[a] = max(mx[a], pos[i][a]);
mx[b] = max(mx[b], pos[i][b]);
}
for (int i=1; i<=3; i++) {
novi(i, pos[i][a]);
novi(i, pos[i][b]);
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i=1; i<=3; i++) {
for (int j=1; j<=n; j++) {
cin >> p[i][j];
pos[i][p[i][j]] = j;
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=3; j++) {
mx[i] = max(mx[i], pos[j][i]);
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=3; j++) {
val[i] = max(val[i], mx[p[j][i]]);
}
}
build();
//ispis();
for (int i=0; i<q; i++) {
int tip;
cin >> tip;
if (tip == 1) {
int a;
cin >> a;
int lim = upit(1, 0, n-1, 0, ofs-1).pos + 1;
if (mx[a] <= lim) cout << "DA\n"; else cout << "NE\n";
} else {
int r, a, b;
cin >> r >> a >> b;
promjeni(r, a, b);
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
65 ms |
6596 KB |
Output is correct |
14 |
Correct |
71 ms |
6584 KB |
Output is correct |
15 |
Correct |
65 ms |
6576 KB |
Output is correct |
16 |
Correct |
62 ms |
6600 KB |
Output is correct |
17 |
Correct |
61 ms |
6520 KB |
Output is correct |
18 |
Correct |
57 ms |
6544 KB |
Output is correct |
19 |
Correct |
55 ms |
6524 KB |
Output is correct |
20 |
Correct |
67 ms |
6648 KB |
Output is correct |
21 |
Correct |
55 ms |
6648 KB |
Output is correct |
22 |
Correct |
63 ms |
6520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
6904 KB |
Output is correct |
2 |
Correct |
107 ms |
6916 KB |
Output is correct |
3 |
Correct |
106 ms |
6876 KB |
Output is correct |
4 |
Correct |
98 ms |
6948 KB |
Output is correct |
5 |
Correct |
125 ms |
6820 KB |
Output is correct |
6 |
Correct |
98 ms |
6876 KB |
Output is correct |
7 |
Correct |
108 ms |
6904 KB |
Output is correct |
8 |
Correct |
99 ms |
6908 KB |
Output is correct |
9 |
Correct |
109 ms |
6904 KB |
Output is correct |
10 |
Correct |
121 ms |
6904 KB |
Output is correct |
11 |
Correct |
117 ms |
6940 KB |
Output is correct |
12 |
Correct |
112 ms |
6888 KB |
Output is correct |
13 |
Correct |
109 ms |
6904 KB |
Output is correct |
14 |
Correct |
118 ms |
6960 KB |
Output is correct |
15 |
Correct |
118 ms |
6868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
65 ms |
6596 KB |
Output is correct |
14 |
Correct |
71 ms |
6584 KB |
Output is correct |
15 |
Correct |
65 ms |
6576 KB |
Output is correct |
16 |
Correct |
62 ms |
6600 KB |
Output is correct |
17 |
Correct |
61 ms |
6520 KB |
Output is correct |
18 |
Correct |
57 ms |
6544 KB |
Output is correct |
19 |
Correct |
55 ms |
6524 KB |
Output is correct |
20 |
Correct |
67 ms |
6648 KB |
Output is correct |
21 |
Correct |
55 ms |
6648 KB |
Output is correct |
22 |
Correct |
63 ms |
6520 KB |
Output is correct |
23 |
Correct |
108 ms |
6904 KB |
Output is correct |
24 |
Correct |
107 ms |
6916 KB |
Output is correct |
25 |
Correct |
106 ms |
6876 KB |
Output is correct |
26 |
Correct |
98 ms |
6948 KB |
Output is correct |
27 |
Correct |
125 ms |
6820 KB |
Output is correct |
28 |
Correct |
98 ms |
6876 KB |
Output is correct |
29 |
Correct |
108 ms |
6904 KB |
Output is correct |
30 |
Correct |
99 ms |
6908 KB |
Output is correct |
31 |
Correct |
109 ms |
6904 KB |
Output is correct |
32 |
Correct |
121 ms |
6904 KB |
Output is correct |
33 |
Correct |
117 ms |
6940 KB |
Output is correct |
34 |
Correct |
112 ms |
6888 KB |
Output is correct |
35 |
Correct |
109 ms |
6904 KB |
Output is correct |
36 |
Correct |
118 ms |
6960 KB |
Output is correct |
37 |
Correct |
118 ms |
6868 KB |
Output is correct |
38 |
Correct |
358 ms |
6828 KB |
Output is correct |
39 |
Correct |
161 ms |
9188 KB |
Output is correct |
40 |
Correct |
426 ms |
9536 KB |
Output is correct |
41 |
Correct |
148 ms |
9220 KB |
Output is correct |
42 |
Correct |
160 ms |
9292 KB |
Output is correct |
43 |
Correct |
344 ms |
9336 KB |
Output is correct |
44 |
Correct |
132 ms |
9208 KB |
Output is correct |
45 |
Correct |
184 ms |
9336 KB |
Output is correct |
46 |
Correct |
153 ms |
9208 KB |
Output is correct |
47 |
Correct |
153 ms |
9208 KB |
Output is correct |
48 |
Correct |
151 ms |
9336 KB |
Output is correct |
49 |
Correct |
174 ms |
9320 KB |
Output is correct |
50 |
Correct |
133 ms |
9208 KB |
Output is correct |
51 |
Correct |
158 ms |
9336 KB |
Output is correct |
52 |
Correct |
337 ms |
9392 KB |
Output is correct |
53 |
Correct |
128 ms |
9336 KB |
Output is correct |
54 |
Correct |
169 ms |
9236 KB |
Output is correct |
55 |
Correct |
173 ms |
9268 KB |
Output is correct |
56 |
Correct |
159 ms |
9208 KB |
Output is correct |
57 |
Correct |
141 ms |
9208 KB |
Output is correct |
58 |
Correct |
266 ms |
9236 KB |
Output is correct |