#include <bits/stdc++.h>
using namespace std;
//#define TEST
#ifdef TEST
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
#endif // TEST
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
const int len = 2e5+5;
vector<int> adj[len];
int nex[len], nod[len], fir[len], tree[2*len];
ii inter[len];
void update(int p, int l, int r, int i, int v){
if (l == r)
tree[p] += v;
else{
int mid = (l+r)/2;
if (i <= mid)
update(2*p, l, mid, i, v);
else
update(2*p+1, mid+1, r, i, v);
tree[p] = tree[2*p] + tree[2*p+1];
}
}
int query(int p, int l, int r, int k){
//printf("(l, r) = (%d, %d), k = %d\n", l, r, k);
if (l == r)
return l;
int mid = (l+r)/2;
if (k <= tree[2*p])
return query(2*p, l, mid, k);
return query(2*p+1, mid+1, r, k-tree[2*p]);
}
ii dfs(int u){
if (adj[u].size() == 0) return mp(0, u);
ii ans = mp(-1, -1);
int temp = (fir[inter[u].fi] >= inter[u].se);
for (int j = 0; j < adj[u].size(); j++){
int v = adj[u][j];
//out[v] = out[u]+temp;
ii cur = dfs(v);
if (cur.fi > ans.fi)
ans = cur;
else if (cur.fi == ans.fi && cur.se < ans.se)
ans = cur;
}
ans.fi += temp;
return ans;
}
int GetBestPosition(int n, int q, int p, int *arr, int *st, int *en){
int m = n-1;
for (int i = 0; i < n; i++){
nex[i] = i+1;
nod[i] = i;
}
for (int i = 0; i < n; i++)
update(1, 0, n-1, i, 1);
for (int i = 0; i < q; i++){
int beg = query(1, 0, n-1, st[i]+1), pos = beg, rem = en[i]-st[i];
++m;
update(1, 0, n-1, beg, 1);
while (rem--){
update(1, 0, n-1, pos, -1);
adj[m].pb(nod[pos]);
pos = nex[pos];
}
adj[m].pb(nod[pos]);
update(1, 0, n-1, pos, -1);
nex[beg] = nex[pos];
nod[beg] = m;
inter[m] = mp(beg, nex[beg]-1);
//printf("beg = %d, end = %d\n", beg, nex[beg]-1);
}
/*for (int i = 0; i <= m; i++){
printf("%d(%d, %d):", i, inter[i].fi, inter[i].se);
for (int j = 0; j < adj[i].size(); j++)
printf(" %d", adj[i][j]);
printf("\n");
}*/
arr[n-1] = n;
for (int i = 0, j = 0; i < n; i++){
j = max(j, i);
while (arr[j] <= p)
j++;
fir[i] = j;
//printf("i = %d, j = %d\n", i, j);
}
//printf("%d, %d\n", dfs(m).fi, dfs(m).se);
/*ii temp = dfs(m);
ii ans = mp(-1, -1);
for (int i = 0; i < n; i++)
if (out[i] > ans.fi || (out[i] == ans.fi && i < ans.se))
ans = mp(out[i], i);*/
//for (int i = 0; i < n; i++)
// printf("%d ", out[i]);
//printf("\n");
return dfs(m).se;
}
#ifdef TEST
int main() {
//freopen("example.txt", "r", stdin);
int tmp;
/* Set input and output buffering */
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
assert(tmp == 0);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
assert(tmp == 0);
int N, C, R;
int *K, *S, *E;
tmp = scanf("%d %d %d", &N, &C, &R);
assert(tmp == 3);
K = (int*) malloc((N-1) * sizeof(int));
S = (int*) malloc(C * sizeof(int));
E = (int*) malloc(C * sizeof(int));
int i;
for (i = 0; i < N-1; i++) {
tmp = scanf("%d", &K[i]);
assert(tmp == 1);
}
for (i = 0; i < C; i++) {
tmp = scanf("%d %d", &S[i], &E[i]);
assert(tmp == 2);
}
printf("%d\n", GetBestPosition(N, C, R, K, S, E));
return 0;
}
#endif // TEST
/*
8 5 3
0 1 2 4 5 6 7
1 3
2 3
3 4
0 2
0 1
5 4 2
0 1 3 4
0 1
0 1
0 1
0 1
*/
Compilation message
tournament.cpp: In function 'ii dfs(int)':
tournament.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[u].size(); j++){
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5308 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5308 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5308 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5308 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5308 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
11 ms |
6120 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6120 KB |
Output is correct |
| 4 |
Correct |
11 ms |
6120 KB |
Output is correct |
| 5 |
Correct |
12 ms |
6120 KB |
Output is correct |
| 6 |
Correct |
12 ms |
6164 KB |
Output is correct |
| 7 |
Correct |
11 ms |
6332 KB |
Output is correct |
| 8 |
Correct |
11 ms |
6332 KB |
Output is correct |
| 9 |
Correct |
10 ms |
6332 KB |
Output is correct |
| 10 |
Correct |
12 ms |
6364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
9372 KB |
Output is correct |
| 2 |
Correct |
161 ms |
19576 KB |
Output is correct |
| 3 |
Correct |
65 ms |
19576 KB |
Output is correct |
| 4 |
Correct |
181 ms |
19576 KB |
Output is correct |
| 5 |
Correct |
166 ms |
21728 KB |
Output is correct |
| 6 |
Correct |
144 ms |
21728 KB |
Output is correct |
| 7 |
Correct |
129 ms |
24664 KB |
Output is correct |
| 8 |
Correct |
122 ms |
26352 KB |
Output is correct |
| 9 |
Correct |
55 ms |
26352 KB |
Output is correct |
| 10 |
Correct |
70 ms |
26352 KB |
Output is correct |
