Submission #66906

#TimeUsernameProblemLanguageResultExecution timeMemory
66906KLPPJousting tournament (IOI12_tournament)C++14
49 / 100
1083 ms86660 KiB
#include<iostream> #include<vector> #include<stdio.h> #include<queue> using namespace std; vector<int> nei[3000000]; int n,c,r; int arr [3000000]; int ansL[3000000]; int ansR[3000000]; int maxchain[3000000]; int index[3000000]; class FT{ private:vector<int> ft; public: FT(int n){ft.assign(n+1,0);} int rsq(int b){ int ans=0; for(;b;b-=(b&(-b)))ans+=ft[b]; return ans; } void update(int k, int v){ for(;k<(int)ft.size();k+=(k&(-k)))ft[k]+=v; } };//OK int DPl(int node){ if(node==n-1){ ansL[node]=0; return 0; } if(node<n-1){ ansL[node]=arr[node]; return arr[node]; } ansL[node]=n; for(int i=0;i<(int)nei[node].size();i++){ int v=nei[node][i]; ansL[node]=min(ansL[node],DPl(v)); } return ansL[node]; }//OK int DPr(int node){ if(node==0){ ansR[node]=0; return 0; } if(node<n){ ansR[node]=arr[node-1]; return arr[node-1]; } ansR[node]=n; for(int i=0;i<(int)nei[node].size();i++){ int v=nei[node][i]; ansR[node]=min(ansR[node],DPr(v)); } return ansR[node]; }//OK int ChainDP(int node){ if(maxchain[node]!=-1){ return maxchain[node]; } if(node<n){ index[node]=node; maxchain[node]=0; return 0; } int ans=0; int DPright[nei[node].size()]; int DPleft[nei[node].size()]; DPleft[0]=n+1; for(int i=0;i<(int)nei[node].size()-1;i++){ int v=nei[node][i]; DPleft[i+1]=min(DPleft[i],DPl(v)); } DPright[nei[node].size()-1]=n+1; for(int i=nei[node].size()-1;i>0;i--){ int v=nei[node][i]; DPright[i-1]=min(DPright[i],DPr(v)); } index[node]=-1; for(int i=0;i<(int)nei[node].size();i++){ if(min(r,DPleft[i])==r && min(r,DPright[i])==r && ans<1+ChainDP(nei[node][i])){ ans=max(ans,1+ChainDP(nei[node][i])); index[node]=index[nei[node][i]]; } } if(ans==0)ans=-1000000000; maxchain[node]=ans; return ans; } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {int maximo=-1; n=N; c=C; r=R; r=n-r; for(int i=0;i<n-1;i++){ arr[i]=K[i]; arr[i]=n-arr[i]; } int counter=n; int pointer[n]; int next[n]; for(int i=0;i<n;i++){ pointer[i]=i; next[i]=i+1; } FT a(n); int parent[1000000]; for(int i=0;i<c;i++){//OK int x,y; x=S[i]; y=E[i]; int hi,lo; lo=-1; hi=n; while(hi-lo>1){ int mid=(hi+lo)/2; if(a.rsq(mid+1)+mid<x)lo=mid; else hi=mid; } int start=hi; nei[counter].push_back(pointer[hi]); parent[pointer[hi]]=counter; while(y>x){ hi=next[hi]; a.update(hi+1,-1); y--; nei[counter].push_back(pointer[hi]); parent[pointer[hi]]=counter; } hi=next[hi]; next[start]=hi; pointer[start]=counter; //for(int j=0;j<n;j++)cout<<pointer[j]<<" "<<next[j]<<endl; counter++; //for(int j=0;j<n;j++)cout<<a.rsq(j+1)+j<<" "; //cout<<endl; } /*for(int i=n;i<n+c;i++){ for(int j=0;j<nei[i].size();j++)cout<<nei[i][j]<<" "; cout<<endl; }*/ //DP DPl(n+c-1); //for(int i=0;i<n+c;i++)cout<<ansL[i]<<endl; DPr(n+c-1); //for(int i=0;i<n+c;i++)cout<<ansR[i]<<endl; for(int i=0;i<n+c;i++)maxchain[i]=-1; for(int i=0;i<n+c;i++)ChainDP(i); //for(int i=0;i<n+c;i++)cout<<maxchain[i]<<endl; //for(int i=0;i<n+c;i++)cout<<index[i]<<endl; queue<int> q; for(int i=0;i<n+c;i++){//cout<<maxchain[i]<<endl; if(maximo==maxchain[i]){ q.push(i); } if(maximo<maxchain[i]){ while(!q.empty())q.pop(); q.push(i); maximo=maxchain[i]; } } while(index[q.front()]!=q.front()){ q.push(index[q.front()]); q.pop(); } int minimo=2*n; while(!q.empty()){//cout<<q.front()<<endl; minimo=min(minimo,q.front()); q.pop(); } return minimo; }

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:109:6: warning: variable 'parent' set but not used [-Wunused-but-set-variable]
  int parent[1000000];
      ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...