Submission #59564

#	Time	Username	Problem	Language	Result	Execution time	Memory
59564		KLPP	Jousting tournament (IOI12_tournament)	C++14	0 / 100	210 ms	75072 KiB

tournament

#include<iostream>
#include<vector>
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;
		}
	
};
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];
}
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];
}
int ChainDP(int node){
	if(maxchain[node]!=-1){
		return maxchain[node];
	}
	if(node<n){
		index[node]=-1;
		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]=nei[node][i];
		}
	}
	if(ans==0)ans=-1;
	maxchain[node]=ans;
	return ans;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	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);
	for(int i=0;i<c;i++){
		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]);
		while(y>x){
			hi=next[hi];
			a.update(hi+1,-1);
			y--;
			nei[counter].push_back(pointer[hi]);
		}
		hi=next[hi];
		next[start]=hi;
		pointer[start]=counter;
		
		counter++;
		
	}
	
	DPl(n+c-1);
	
	DPr(n+c-1);
	
	for(int i=0;i<n+c;i++)maxchain[i]=-1;
	for(int i=0;i<n+c;i++)ChainDP(i);
	int maximo=0;
	for(int i=0;i<n+c;i++){
		if(maxchain[maximo]<maxchain[i])maximo=i;
	}
	while(index[maximo]!=-1){
		maximo=index[maximo];
	}
	return maximo;

}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51