Submission #1019897

#TimeUsernameProblemLanguageResultExecution timeMemory
1019897pccJousting tournament (IOI12_tournament)C++17
0 / 100
71 ms20812 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> using namespace __gnu_pbds; using namespace std; #define pii pair<int,int> #define fs first #define sc second const int mxn = 2e5+10; template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; vector<int> tr[mxn]; int par[mxn][20],dep[mxn]; pii arr[mxn]; vector<pii> rng; ordered_set<pii> st; void dfs(int now){ for(int i = 1;i<20;i++){ par[now][i] = par[par[now][i-1]][i-1]; } for(auto nxt:tr[now]){ dep[nxt] = dep[now]+1; par[nxt][0] = now; dfs(nxt); } return; } int up(int now,int l,int r){ int lim = dep[now]; int ans = 0; for(int i = 19;i>=0;i--){ int p = par[now][i]; if(arr[p].fs>l&&arr[p].sc<r){ now = p; ans += 1<<i; } } return min(ans,lim); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { for(int i = 0;i<C;i++){ rng.push_back(pii(S[i],E[i])); } int ptr = N; for(int i = 0;i<=N;i++)st.insert(pii(i,i)),arr[i] = pii(i,i); for(auto &i:rng){ ptr++; auto lit = st.find_by_order(i.fs); auto rit = st.find_by_order(i.sc+1); arr[ptr].fs = arr[lit->sc].fs; arr[ptr].sc = arr[rit->sc].fs-1; for(auto it = lit;it != rit;it++){ tr[ptr].push_back(it->sc); } int tmp = lit->fs; auto it = lit; while((it = st.find_by_order(i.fs))->fs<=arr[ptr].sc)st.erase(it); st.insert(pii(tmp,ptr)); } assert(st.size() == 2); par[ptr][0] = ptr; dfs(ptr); std::priority_queue<int,vector<int>,greater<int>> pq; pq.push(N); for(int i = 0;i+1<N;i++){ if(K[i]>R)pq.push(i); } int pl = -1,pr = pq.top(); int ans = 0; for(int i = 0;i<N;i++){ if(pq.top()<i){ pl = pq.top(); pq.pop(); } pr = pq.top(); ans = max(ans,up(i,pl,pr+1)); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...