# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
584832 |
2022-06-28T04:39:44 Z |
AngusRitossa |
Teams (IOI15_teams) |
C++14 |
|
4000 ms |
500048 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct ptreenode
{
int left, right, val; // val = num
};
ptreenode ptree[20000000];
int upto;
void pupdate(int node, int curr, int oldcurr, int cstart = 0, int cend = 500010)
{
if (cstart == cend)
{
ptree[curr].val = ptree[oldcurr].val+1;
return;
}
int mid = (cstart+cend)/2;
if (node <= mid)
{
ptree[curr].left = ++upto;
ptree[curr].right = ptree[oldcurr].right;
pupdate(node, ptree[curr].left, ptree[oldcurr].left, cstart, mid);
}
else
{
ptree[curr].right = ++upto;
ptree[curr].left = ptree[oldcurr].left;
pupdate(node, ptree[curr].right, ptree[oldcurr].right, mid+1, cend);
}
ptree[curr].val = ptree[ptree[curr].left].val + ptree[ptree[curr].right].val;
}
int pquery(int s, int e, int curr, int cstart = 0, int cend = 500010)
{
if (s <= cstart && cend <= e) return ptree[curr].val;
int mid = (cstart+cend)/2;
if (e <= mid) return pquery(s, e, ptree[curr].left, cstart, mid);
else if (s > mid) return pquery(s, e, ptree[curr].right, mid+1, cend);
else return pquery(s, e, ptree[curr].left, cstart, mid) + pquery(s, e, ptree[curr].right, mid+1, cend);
}
struct otreenode
{
int left, right, val, last, lazy; // val = last in its subtree;
};
otreenode otree[20000000];
int upto2, n;
int roots[500010];
void push(int curr, int cstart, int mid, int cend)
{
if (!otree[curr].left) otree[curr].left = ++upto2;
if (!otree[curr].right) otree[curr].right = ++upto2;
if (!otree[curr].lazy) return;
int l = otree[curr].left;
int r = otree[curr].right;
otree[l].last = otree[r].last = otree[l].lazy = otree[r].lazy = otree[curr].lazy;
int a = pquery(cstart, mid, roots[otree[curr].lazy]);
int b = pquery(mid+1, cend, roots[otree[curr].lazy]);
// printf("%d %d %d a %d b %d\n", cstart, mid, cend, a, b);
otree[l].val = a;
otree[r].val = b;
otree[curr].lazy = 0;
}
void oupdate(int s, int e, int val, int curr, int cstart = 0, int cend = 500010)
{
if (s <= cstart && cend <= e)
{
// printf("updating %d %d %d\n", cstart, cend, val);
otree[curr].last = otree[curr].lazy = val;
int a = pquery(cstart, cend, roots[val]);
otree[curr].val = a;
// printf("a %d\n", a);
return;
}
int mid = (cstart+cend)/2;
push(curr, cstart, mid, cend);
if (e <= mid) oupdate(s, e, val, otree[curr].left, cstart, mid);
else if (s > mid) oupdate(s, e, val, otree[curr].right, mid+1, cend);
else
{
oupdate(s, e, val, otree[curr].left, cstart, mid);
oupdate(s, e, val, otree[curr].right, mid+1, cend);
}
otree[curr].val = otree[otree[curr].left].val + otree[otree[curr].right].val;
otree[curr].last = otree[otree[curr].right].last;
}
int treewalkfindfirstbelow(int val, int curr, int cstart = 0, int cend = 500010)
{
if (cstart == cend) return cstart;
int mid = (cstart+cend)/2;
push(curr, cstart, mid, cend);
if (otree[otree[curr].left].last <= val) return treewalkfindfirstbelow(val, otree[curr].left, cstart, mid);
else return treewalkfindfirstbelow(val, otree[curr].right, mid+1, cend);
}
int ROOT;
int othertreewalk(int amreq, int e, int curr, int cstart = 0, int cend = 500010, int amtoside = 0)
{
if (cstart == cend)
{
amtoside += otree[curr].val;
int hei = otree[curr].last;
//printf("%d %d %d - %d %d\n", amreq, e, cstart, pquery(cstart, e, roots[n]), amtoside);
if (pquery(cstart, e, roots[n])-amtoside < amreq)
{
// Impossible
// what a shame
return 0;
}
int S = hei;
int E = n;
while (S != E)
{
int mid = (S+E)/2;
if (pquery(cstart, e, roots[mid])-amtoside < amreq) S = mid+1;
else E = mid;
}
// printf("%d %d %d - %d, %d %d\n", cstart, e, S, amreq, pquery(cstart, e, roots[S]), amtoside);
oupdate(cstart, e, S, ROOT);
return 1;
}
int mid = (cstart+cend)/2;
push(curr, cstart, mid, cend);
// consider last in left subtree
int h = otree[otree[curr].left].last;
int am = -1;
if (mid+1 <= e) am = pquery(mid+1, e, roots[h]) - otree[otree[curr].right].val - amtoside;
// printf("%d %d am %d - %d mid+1, e, %d %d - query %d right val %d, amtoside %d\n", cstart, cend, am, h, mid+1, e, am+otree[otree[curr].right].val + amtoside, otree[otree[curr].right].val, amtoside);
if (am < amreq) // have to go to left
{
amtoside += otree[otree[curr].right].val;
return othertreewalk(amreq, e, otree[curr].left, cstart, mid, amtoside);
}
else
{
return othertreewalk(amreq, e, otree[curr].right, mid+1, cend, amtoside);
}
}
int lastA[500010];
int lastB[500010];
int x[500010], y[500010];
void init(int N, int A[], int B[]) {
n = N;
fill_n(lastA, 500010, 0);
fill_n(lastB, 500010, 0);
vector<pair<int, int> > sortedbyA;
for (int i = 0; i < n; i++)
{
sortedbyA.emplace_back(A[i], i);
}
sort(sortedbyA.begin(), sortedbyA.end());
for (int i = 0; i < n; i++)
{
if (i == n-1)
{
for (int j = sortedbyA[i].first; j <= N; j++) lastA[j] = i+1;
}
else if (sortedbyA[i].first != sortedbyA[i+1].first)
{
for (int j = sortedbyA[i].first; j < sortedbyA[i+1].first; j++)
{
lastA[j] = i+1;
}
}
x[sortedbyA[i].second] = i+1;
}
sortedbyA.clear();
for (int i = 0; i < n; i++)
{
sortedbyA.emplace_back(B[i], i);
}
sort(sortedbyA.begin(), sortedbyA.end());
for (int i = 0; i < n; i++)
{
if (i == n-1)
{
for (int j = sortedbyA[i].first; j <= N; j++) lastB[j] = i+1;
}
else if (sortedbyA[i].first != sortedbyA[i+1].first)
{
for (int j = sortedbyA[i].first; j < sortedbyA[i+1].first; j++)
{
lastB[j] = i+1;
}
}
y[sortedbyA[i].second] = i+1;
}
sortedbyA.clear();
for (int i = 0; i < n; i++)
{
// printf("%d %d\n", x[i], y[i]);
sortedbyA.emplace_back(y[i], x[i]);
}
sort(sortedbyA.begin(), sortedbyA.end());
for (auto a : sortedbyA)
{
// assert(!roots[a.first]);
roots[a.first] = ++upto;
// printf("at %d - updating %d\n", a.first, a.second);
pupdate(a.second, roots[a.first], roots[a.first-1]);
// printf("%d\n", pquery(0, n, roots[a.first]));
}
}
int can(int m, int k[]) {
sort(k, k+m);
int r = ++upto2;
ROOT = r;
for (int i = 0; i < m; i++)
{
int a = lastA[k[i]];
int b = lastB[k[i]-1];
int s = treewalkfindfirstbelow(b, r);
// printf("%d\n", s);
if (s <= n) oupdate(s, n, b, r);
int res = othertreewalk(k[i], a, r);
if (!res) return 0;
}
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4152 KB |
Output is correct |
2 |
Correct |
2 ms |
4180 KB |
Output is correct |
3 |
Correct |
2 ms |
4308 KB |
Output is correct |
4 |
Correct |
3 ms |
4308 KB |
Output is correct |
5 |
Correct |
2 ms |
4308 KB |
Output is correct |
6 |
Correct |
2 ms |
4308 KB |
Output is correct |
7 |
Correct |
7 ms |
4436 KB |
Output is correct |
8 |
Correct |
5 ms |
4460 KB |
Output is correct |
9 |
Correct |
3 ms |
4308 KB |
Output is correct |
10 |
Correct |
6 ms |
4436 KB |
Output is correct |
11 |
Correct |
4 ms |
4180 KB |
Output is correct |
12 |
Correct |
14 ms |
4436 KB |
Output is correct |
13 |
Correct |
7 ms |
4416 KB |
Output is correct |
14 |
Correct |
6 ms |
4436 KB |
Output is correct |
15 |
Correct |
3 ms |
4408 KB |
Output is correct |
16 |
Correct |
4 ms |
4308 KB |
Output is correct |
17 |
Correct |
5 ms |
4308 KB |
Output is correct |
18 |
Correct |
3 ms |
4308 KB |
Output is correct |
19 |
Correct |
5 ms |
4336 KB |
Output is correct |
20 |
Correct |
4 ms |
4356 KB |
Output is correct |
21 |
Correct |
3 ms |
4308 KB |
Output is correct |
22 |
Correct |
4 ms |
4280 KB |
Output is correct |
23 |
Correct |
3 ms |
4308 KB |
Output is correct |
24 |
Correct |
3 ms |
4308 KB |
Output is correct |
25 |
Correct |
3 ms |
4308 KB |
Output is correct |
26 |
Correct |
4 ms |
4308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
31632 KB |
Output is correct |
2 |
Correct |
83 ms |
31620 KB |
Output is correct |
3 |
Correct |
82 ms |
31664 KB |
Output is correct |
4 |
Correct |
88 ms |
31860 KB |
Output is correct |
5 |
Correct |
77 ms |
31288 KB |
Output is correct |
6 |
Correct |
73 ms |
31232 KB |
Output is correct |
7 |
Correct |
63 ms |
31308 KB |
Output is correct |
8 |
Correct |
65 ms |
31312 KB |
Output is correct |
9 |
Correct |
246 ms |
31300 KB |
Output is correct |
10 |
Correct |
158 ms |
31044 KB |
Output is correct |
11 |
Correct |
60 ms |
31164 KB |
Output is correct |
12 |
Correct |
52 ms |
31196 KB |
Output is correct |
13 |
Correct |
68 ms |
31476 KB |
Output is correct |
14 |
Correct |
77 ms |
31424 KB |
Output is correct |
15 |
Correct |
70 ms |
31560 KB |
Output is correct |
16 |
Correct |
66 ms |
31672 KB |
Output is correct |
17 |
Correct |
67 ms |
31540 KB |
Output is correct |
18 |
Correct |
69 ms |
31624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
31876 KB |
Output is correct |
2 |
Correct |
78 ms |
31936 KB |
Output is correct |
3 |
Correct |
1197 ms |
200128 KB |
Output is correct |
4 |
Correct |
76 ms |
31804 KB |
Output is correct |
5 |
Correct |
909 ms |
59836 KB |
Output is correct |
6 |
Correct |
795 ms |
57016 KB |
Output is correct |
7 |
Correct |
69 ms |
31552 KB |
Output is correct |
8 |
Correct |
606 ms |
50544 KB |
Output is correct |
9 |
Correct |
210 ms |
31292 KB |
Output is correct |
10 |
Correct |
609 ms |
31168 KB |
Output is correct |
11 |
Correct |
726 ms |
31716 KB |
Output is correct |
12 |
Correct |
928 ms |
52496 KB |
Output is correct |
13 |
Correct |
1366 ms |
83092 KB |
Output is correct |
14 |
Correct |
1274 ms |
152180 KB |
Output is correct |
15 |
Correct |
472 ms |
56652 KB |
Output is correct |
16 |
Correct |
498 ms |
57816 KB |
Output is correct |
17 |
Correct |
488 ms |
51072 KB |
Output is correct |
18 |
Correct |
524 ms |
47336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
455 ms |
141888 KB |
Output is correct |
2 |
Correct |
445 ms |
141900 KB |
Output is correct |
3 |
Correct |
3318 ms |
500048 KB |
Output is correct |
4 |
Correct |
473 ms |
141844 KB |
Output is correct |
5 |
Correct |
2589 ms |
203144 KB |
Output is correct |
6 |
Correct |
2310 ms |
196544 KB |
Output is correct |
7 |
Correct |
335 ms |
139184 KB |
Output is correct |
8 |
Correct |
1933 ms |
184740 KB |
Output is correct |
9 |
Correct |
1457 ms |
139708 KB |
Output is correct |
10 |
Correct |
1875 ms |
137900 KB |
Output is correct |
11 |
Correct |
2212 ms |
143200 KB |
Output is correct |
12 |
Correct |
2948 ms |
197984 KB |
Output is correct |
13 |
Execution timed out |
4054 ms |
252492 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |