제출 #282367

#제출 시각아이디문제언어결과실행 시간메모리
282367amiratou마상시합 토너먼트 (IOI12_tournament)C++14
49 / 100
1089 ms45252 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl; #define sep() cerr << "--------------------" << endl; const int MX = 100005, INF = (int)(1e9) , L = 18; typedef pair<int,int> ii; int fen[MX],Ry[MX],up[2*MX][L],d[2*MX],ST[4*MX],KK[MX],n,ans=-1,ARG; vector<int> vec[2*MX]; ii ranges[2*MX]; void update(int idx,int val){ for (int i = idx; i <= n; i+=(i&(-i))) fen[i]+=val; } int get(int idx){ int h=0; for (int i = idx; i >= 1; i-=(i&(-i))) h+=fen[i]; return h; } int gimme(int nb,int l=0,int r=n-1){ int ans=-1; while(l<=r){ int med=(l+r)>>1; if(get(med+1)>=nb) ans=med,r=med-1; else l=med+1; } assert(ans!=-1); return ans; } void dfs(int node,int p){ up[node][0]=p; for (int i = 1; i < L; ++i) up[node][i]=up[up[node][i-1]][i-1]; for(auto it:vec[node]) d[it]=d[node]+1,dfs(it,node); } void build(int node,int l,int r){ if(l==r){ ST[node]=KK[l]; return; } int med=(l+r)>>1; build(node*2,l,med),build(node*2+1,med+1,r); ST[node]=max(ST[node*2],ST[node*2+1]); } int query(int node,int l,int r,int i,int j){ if(l>j || r<i)return -1; if(l>=i && r<=j)return ST[node]; int med=(l+r)>>1; return max(query(node*2,l,med,i,j),query(node*2+1,med+1,r,i,j)); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { set<int> alive; set<pair<ii,int> > myset; n=N; for (int i = 0; i < N; ++i) { up[i+C][0]=-1; ranges[C+i]={i,i}; if(i!=(N-1))KK[i]=K[i]; myset.insert({{i,-i},C+i}); alive.insert(i); update(i+1,1),Ry[i]=i; } for (int i = 0; i < C; ++i) { up[i][0]=-1; int st=gimme(S[i]+1),e=gimme(E[i]+1); e=Ry[e]; auto it=alive.lower_bound(st); while(it!=alive.end() && (*it)<=e) update(*it+1,-1),it=alive.erase(it); update(st+1,1),alive.insert(st),Ry[st]=e; ranges[i]={st,e}; myset.insert({{st,-e},i}); } vector<int> order; while(!myset.empty()){ pair<ii,int> it=*myset.begin(); order.push_back(it.se); myset.erase(myset.begin()); it.fi.se*=-1; auto k=myset.begin(); while(k!=myset.end() && (-(*k).fi.se)<=it.fi.se){ vec[it.se].push_back(k->se); k=myset.lower_bound({{-(*k).fi.se+1,-INF},-1}); } } for(auto it:order) if(up[it][0]==-1)dfs(it,it); build(1,0,N-2); for (int i = 0; i < N; ++i) { int l=1,r=d[C+i],nb=0; while(l<=r){ int med=(l+r)>>1,node=C+i; for (int j = 0; j < L; ++j) if((med>>j)&1)node=up[node][j]; assert(node<C); int maxi=-1; if(i!=ranges[node].fi)maxi=max(maxi,query(1,0,n-2,ranges[node].fi,i-1)); if(i!=ranges[node].se)maxi=max(maxi,query(1,0,n-2,i,ranges[node].se-1)); if(maxi<R)nb=med,l=med+1; else r=med-1; } if(nb>ans)ans=nb,ARG=i; } return ARG; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...