제출 #43813

#제출 시각아이디문제언어결과실행 시간메모리
43813PowerOfNinjaGo마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
59 ms17452 KiB
//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* 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(node *u, int x, int y, int dest) { node *v, *w; split(u, u, v, y+1); split(u, u, w, x); transfer(dest, w); u = merge(u, new node(dest)); u = merge(u, v); //printf("size is %d\n", u->sz); } void buildseg(int p = 1, int L = 0, int R = n-2) { if(L == R) st[p] = arr[L]; int M = (L+R)/2; buildseg(2*p, L, M); buildseg(2*p, 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; 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) { srand(time(NULL)); n = N; for(int i = 0; i< n-1; i++) arr[i] = k[i]; node *root = NULL; 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, dp[0][i] = -1; for(int i = 0; i< c; i++) { lo[cur] = 1e9, hi[cur] = -1e9; process(root, s[i], e[i], cur); //printf("root is now %d\n", root->sz); 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; 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; int rangeX = lo[tobe], rangeY = hi[tobe]-1; int val = ask(rangeX, rangeY); if(val<= r) { now = tobe; cnt += 1<<p; } } if(cnt> best) { best = cnt; dat = i; } } return dat; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...