//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 1e5+5;
int arr[maxn];
vi adj[2*maxn];
int lo[2*maxn];
int hi[2*maxn];
int st[4*maxn];
int dp[22][2*maxn];
int n;
struct node
{
int v, sz, prio;
node *left, *right;
void upd()
{
sz = 1+(left?left->sz:0)+(right?right->sz:0);
}
node(int a)
{
v = a; left = right = NULL;
prio = (rand()<<16)^rand();
upd();
}
};
node *root = NULL;
node* merge(node *L, node *R)
{
if(!L || !R) return L?L:R;
if(L->prio > R->prio)
{
L->right = merge(L->right, R);
L->upd();
return L;
}
else
{
R->left = merge(L, R->left);
R->upd();
return R;
}
}
void split(node *u, node* &L, node* &R, int cur)
{
L = R = NULL;
if(!u) return;
int k = 1+(u->left?u->left->sz:0);
if(k<= cur)
{
L = u;
split(u->right, u->right, R, cur-k);
}
else
{
R = u;
split(u->left, L, u->left, cur);
}
u->upd();
}
void transfer(int dest, node *u)
{
if(u == NULL) return;
lo[dest] = min(lo[dest], lo[u->v]);
hi[dest] = max(hi[dest], hi[u->v]);
adj[dest].pb(u->v);
//printf("connect %d to %d\n", dest, u->v);
transfer(dest, u->left); transfer(dest, u->right);
}
void process(int x, int y, int dest)
{
node *v, *w;
split(root, root, v, y+1);
split(root, root, w, x);
transfer(dest, w);
root = merge(root, new node(dest));
root = merge(root, v);
//printf("%d\n", u->sz);
}
void buildseg(int p = 1, int L = 0, int R = n-2)
{
if(L == R)
{
st[p] = arr[L];
return;
}
int M = (L+R)/2;
buildseg(2*p, L, M); buildseg(2*p+1, M+1, R);
st[p] = max(st[2*p], st[2*p+1]);
}
int ask(int i, int j, int p = 1, int L = 0, int R = n-2)
{
if(i> R || j< L) return 0;
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
int x = ask(i, j, 2*p, L, M); int y = ask(i, j, 2*p+1, M+1, R);
return max(x, y);
}
void dfs(int u)
{
for(auto v : adj[u])
{
dp[0][v] = u;
dfs(v);
}
}
void trav(node *u)
{
if(u == NULL) return;
//printf("trav %d\n", u->v);
dp[0][u->v] = -1;
dfs(u->v);
trav(u->left); trav(u->right);
}
int GetBestPosition(int N, int c, int r, int *k, int *s, int *e)
{
n = N;
for(int i = 0; i< n-1; i++) arr[i] = k[i];
for(int i = 0; i< n; i++) root = merge(root, new node(i));
int cur = n;
for(int i = 0; i< n; i++) lo[i] = hi[i] = i;
for(int i = 0; i< n; i++) dp[0][i] = -1;
for(int i = 0; i< c; i++)
{
lo[cur] = 1e9, hi[cur] = -1e9;
process(s[i], e[i], cur);
cur++;
}
trav(root);
for(int i = 1; i<= 20; i++)
{
for(int j = 0; j< cur; j++)
{
int x = dp[i-1][j];
if(x == -1) dp[i][j] = -1;
else dp[i][j] = dp[i-1][x];
}
}
int best = 0, dat = 0;
buildseg();
for(int i = 0; i< n; i++)
{
int now = i;
int cnt = 0;
for(int p = 20; p>= 0; p--)
{
int tobe = dp[p][now];
if(tobe == -1) continue;
//printf("%d tobe %d\n", i, tobe);
int rangeX = lo[tobe], rangeY = hi[tobe]-1;
int val = ask(rangeX, rangeY);
//printf("[%d, %d]\n", rangeX, rangeY);
//printf("val is %d\n", val);
if(val<= r)
{
now = tobe;
cnt += 1<<p;
}
}
//printf("%d is %d\n", i, cnt);
if(cnt> best)
{
best = cnt;
dat = i;
}
}
return dat;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5220 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5420 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5440 KB |
Output is correct |
| 5 |
Correct |
12 ms |
5440 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5440 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5552 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5552 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5552 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5596 KB |
Output is correct |
| 2 |
Correct |
28 ms |
7260 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7260 KB |
Output is correct |
| 4 |
Correct |
22 ms |
7260 KB |
Output is correct |
| 5 |
Correct |
22 ms |
7260 KB |
Output is correct |
| 6 |
Correct |
15 ms |
7260 KB |
Output is correct |
| 7 |
Correct |
26 ms |
7260 KB |
Output is correct |
| 8 |
Correct |
22 ms |
7260 KB |
Output is correct |
| 9 |
Correct |
10 ms |
7260 KB |
Output is correct |
| 10 |
Correct |
17 ms |
7260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
18856 KB |
Output is correct |
| 2 |
Correct |
683 ms |
40740 KB |
Output is correct |
| 3 |
Correct |
198 ms |
40740 KB |
Output is correct |
| 4 |
Correct |
578 ms |
40740 KB |
Output is correct |
| 5 |
Correct |
614 ms |
40740 KB |
Output is correct |
| 6 |
Correct |
272 ms |
40740 KB |
Output is correct |
| 7 |
Correct |
598 ms |
40740 KB |
Output is correct |
| 8 |
Correct |
657 ms |
40740 KB |
Output is correct |
| 9 |
Correct |
145 ms |
40740 KB |
Output is correct |
| 10 |
Correct |
163 ms |
40740 KB |
Output is correct |
