제출 #1066068

#제출 시각아이디문제언어결과실행 시간메모리
1066068ArthuroWich마상시합 토너먼트 (IOI12_tournament)C++17
49 / 100
1077 ms40684 KiB
//#include "tournament.h" #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; struct node { int p = -1, b = 0, w = 1; vector<int> c = {}; }; node t[200005]; int timer, ra, v = 0, succ[200005][20], depth[200005]; void calc(int i) { for (int j : t[i].c) { depth[j+1] = depth[i+1]+1; calc(j); } for (int j : t[i].c) { t[i].b += t[j].b; } } void update(int i) { for (int j : t[i].c) { t[i].b += t[j].b; } if (t[i].p != -1) { t[t[i].p].b = 0; update(t[i].p); } } void initsucc() { for (int j = 1; j < 20; j++) { for (int i = 0; i < 200000; i++) { succ[i][j] = succ[succ[i][j-1]][j-1]; } } } int kthjump(int a, int k) { for (int j = 0; j < 20; j++) { if (k & (1 << j)) { a = succ[a][j]; } } return a; } int lca(int a, int b) { a++; b++; if (depth[a] > depth[b]) { swap(a, b); } b = kthjump(b, depth[b]-depth[a]); if (a == b) { return a; } for (int j = 19; j >= 0; j--) { if (succ[a][j] != succ[b][j]) { a = succ[a][j]; b = succ[b][j]; } } return succ[a][0]-1; } void trav(int i) { i++; for (int j = 19; j >= 0; j--) { if (succ[i][j]-1 < 0) { continue; } if (t[succ[i][j]-1].b == 0) { v += (1<<j); i = succ[i][j]; } } } int GetBestPosition(int n, int m, int r, int k[], int S[], int E[]) { ra = r; indexed_set e; timer = n; int ans = 0, ind = -1; for (int i = 0; i < n; i++) { e.insert({i, i}); } for (int j = 0; j < 20; j++) { for (int i = 0; i <= 200000; i++) { succ[i][j] = 0; } } for (int i = 0; i < n-1; i++) { if (k[i] > r) { t[i+1].b = 1; } } for (int i = 0; i < m; i++) { int le = E[i]-S[i]+1; set<pair<int, int>> todel; pair<int, int> c; auto ind = e.find_by_order(S[i]); int l = INT_MAX; t[timer].w = 1; while(le--) { c = *ind; todel.insert(c); l = min(l, c.first); t[timer].c.push_back(c.second); t[c.second].p = timer; succ[c.second+1][0] = timer+1; ind++; } for (auto c : todel) { e.erase(c); } e.insert({l, timer}); timer++; } initsucc(); int root = timer-1; calc(root); trav(0); ans = v; ind = 0; for (int i = 1; i < n; i++) { swap(t[i-1].b, t[i].b); if (t[i].b != t[i-1].b) { update(i-1); update(i); } v = 0; trav(i); if (v > ans) { ans = v; ind = i; } } return ind; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...