# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
144383 |
2019-08-16T19:06:33 Z |
emilem |
Tenis (COI19_tenis) |
C++14 |
|
218 ms |
7416 KB |
#include <iostream>
#include <vector>
using namespace std;
vector<int> rankAt[4];
vector< pair<int, int> > tree;
vector<int> lazy;
void Build(int v, int vl, int vr, const vector<int>& a)
{
if (vl == vr)
{
tree[v] = make_pair(a[vr], vr);
return;
}
int vm = vl + (vr - vl) / 2;
Build(v * 2, vl, vm, a);
Build(v * 2 + 1, vm + 1, vr, a);
tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
}
void Update(int v, int vl, int vr, int l, int r, int val)
{
/*
if (l == 2 && r == 4)
cerr << "";
*/
if (vl == l && vr == r)
{
tree[v].first += val;
lazy[v] += val;
return;
}
int vm = vl + (vr - vl) / 2;
if (r <= vm)
Update(v * 2, vl, vm, l, r, val);
else if (l > vm)
Update(v * 2 + 1, vm + 1, vr, l, r, val);
else
{
Update(v * 2, vl, vm, l, vm, val);
Update(v * 2 + 1, vm + 1, vr, vm + 1, r, val);
}
tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
tree[v].first += lazy[v];
}
int Query(int v, int vl, int vr, int l, int r)
{
if (vl == l && vr == r)
return tree[v].first;
int vm = vl + (vr - vl) / 2;
if (r <= vm)
return Query(v * 2, vl, vm, l, r) + lazy[v];
else if (l > vm)
return Query(v * 2 + 1, vm + 1, vr, l, r) + lazy[v];
else
return max(Query(v * 2, vl, vm, l, vm), Query(v * 2 + 1, vm + 1, vr, vm + 1, r)) + lazy[v];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, q;
cin >> n >> q;
rankAt[1] = rankAt[2] = rankAt[3] = vector<int>(n + 1);
vector<int> worst(n + 1, 0);
for (int p = 1; p <= 3; ++p)
for (int i = 1; i <= n; ++i)
{
int ranking;
cin >> ranking;
rankAt[p][ranking] = i;
worst[ranking] = max(worst[ranking], i);
}
tree.resize(n * 4);
lazy.resize(n * 4);
vector<int> f(n + 1);
for (int i = 1; i <= n; ++i)
f[i] += i;
Build(1, 1, n, f);
for (int i = 1; i <= n; ++i)
{
Update(1, 1, n, worst[i], n, -1);
/*
for (int ii = 1; ii <= n; ++ii)
cout << Query(1, 1, n, ii, ii) << ' ';
cout << ": " << tree[1].first;
cout << endl;
*/
}
/*
cout << endl;
*/
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int man;
cin >> man;
cout << (worst[man] <= tree[1].second ? "DA\n" : "NE\n");
}
else
{
int p, a, b;
cin >> p >> a >> b;
Update(1, 1, n, worst[a], n, 1);
Update(1, 1, n, worst[b], n, 1);
swap(rankAt[p][a], rankAt[p][b]);
worst[a] = max(max(rankAt[1][a], rankAt[2][a]), rankAt[3][a]);
worst[b] = max(max(rankAt[1][b], rankAt[2][b]), rankAt[3][b]);
Update(1, 1, n, worst[a], n, -1);
Update(1, 1, n, worst[b], n, -1);
}
}
char I;
cin >> I;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
81 ms |
6956 KB |
Output is correct |
14 |
Correct |
82 ms |
7032 KB |
Output is correct |
15 |
Correct |
81 ms |
6904 KB |
Output is correct |
16 |
Correct |
81 ms |
7084 KB |
Output is correct |
17 |
Correct |
80 ms |
6904 KB |
Output is correct |
18 |
Correct |
80 ms |
7032 KB |
Output is correct |
19 |
Correct |
80 ms |
7032 KB |
Output is correct |
20 |
Correct |
81 ms |
7076 KB |
Output is correct |
21 |
Correct |
81 ms |
7032 KB |
Output is correct |
22 |
Correct |
80 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
7288 KB |
Output is correct |
2 |
Correct |
107 ms |
7312 KB |
Output is correct |
3 |
Correct |
109 ms |
7416 KB |
Output is correct |
4 |
Correct |
103 ms |
7288 KB |
Output is correct |
5 |
Correct |
108 ms |
7376 KB |
Output is correct |
6 |
Correct |
106 ms |
7236 KB |
Output is correct |
7 |
Correct |
100 ms |
7312 KB |
Output is correct |
8 |
Correct |
102 ms |
7288 KB |
Output is correct |
9 |
Correct |
101 ms |
7288 KB |
Output is correct |
10 |
Correct |
100 ms |
7264 KB |
Output is correct |
11 |
Correct |
104 ms |
7328 KB |
Output is correct |
12 |
Correct |
101 ms |
7288 KB |
Output is correct |
13 |
Correct |
102 ms |
7288 KB |
Output is correct |
14 |
Correct |
103 ms |
7288 KB |
Output is correct |
15 |
Correct |
102 ms |
7288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
81 ms |
6956 KB |
Output is correct |
14 |
Correct |
82 ms |
7032 KB |
Output is correct |
15 |
Correct |
81 ms |
6904 KB |
Output is correct |
16 |
Correct |
81 ms |
7084 KB |
Output is correct |
17 |
Correct |
80 ms |
6904 KB |
Output is correct |
18 |
Correct |
80 ms |
7032 KB |
Output is correct |
19 |
Correct |
80 ms |
7032 KB |
Output is correct |
20 |
Correct |
81 ms |
7076 KB |
Output is correct |
21 |
Correct |
81 ms |
7032 KB |
Output is correct |
22 |
Correct |
80 ms |
7004 KB |
Output is correct |
23 |
Correct |
103 ms |
7288 KB |
Output is correct |
24 |
Correct |
107 ms |
7312 KB |
Output is correct |
25 |
Correct |
109 ms |
7416 KB |
Output is correct |
26 |
Correct |
103 ms |
7288 KB |
Output is correct |
27 |
Correct |
108 ms |
7376 KB |
Output is correct |
28 |
Correct |
106 ms |
7236 KB |
Output is correct |
29 |
Correct |
100 ms |
7312 KB |
Output is correct |
30 |
Correct |
102 ms |
7288 KB |
Output is correct |
31 |
Correct |
101 ms |
7288 KB |
Output is correct |
32 |
Correct |
100 ms |
7264 KB |
Output is correct |
33 |
Correct |
104 ms |
7328 KB |
Output is correct |
34 |
Correct |
101 ms |
7288 KB |
Output is correct |
35 |
Correct |
102 ms |
7288 KB |
Output is correct |
36 |
Correct |
103 ms |
7288 KB |
Output is correct |
37 |
Correct |
102 ms |
7288 KB |
Output is correct |
38 |
Correct |
214 ms |
7116 KB |
Output is correct |
39 |
Correct |
127 ms |
7204 KB |
Output is correct |
40 |
Correct |
218 ms |
7076 KB |
Output is correct |
41 |
Correct |
146 ms |
7160 KB |
Output is correct |
42 |
Correct |
149 ms |
7288 KB |
Output is correct |
43 |
Correct |
210 ms |
7036 KB |
Output is correct |
44 |
Correct |
130 ms |
7260 KB |
Output is correct |
45 |
Correct |
153 ms |
7160 KB |
Output is correct |
46 |
Correct |
128 ms |
7224 KB |
Output is correct |
47 |
Correct |
147 ms |
7252 KB |
Output is correct |
48 |
Correct |
128 ms |
7108 KB |
Output is correct |
49 |
Correct |
152 ms |
7288 KB |
Output is correct |
50 |
Correct |
124 ms |
7296 KB |
Output is correct |
51 |
Correct |
150 ms |
7160 KB |
Output is correct |
52 |
Correct |
215 ms |
7276 KB |
Output is correct |
53 |
Correct |
141 ms |
7208 KB |
Output is correct |
54 |
Correct |
145 ms |
7232 KB |
Output is correct |
55 |
Correct |
154 ms |
7160 KB |
Output is correct |
56 |
Correct |
144 ms |
7292 KB |
Output is correct |
57 |
Correct |
126 ms |
7220 KB |
Output is correct |
58 |
Correct |
169 ms |
7288 KB |
Output is correct |