This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |