oj.uz

Submission #66906

# Submission time Handle Problem Language Result Execution time Memory
66906 2018-08-12T18:42:59 Z KLPP Jousting tournament (IOI12_tournament) C++14
49 / 100
 1000 ms 86660 KB 
#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

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];
      ^~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 70904 KB Output is correct
2 Correct 61 ms 71012 KB Output is correct
3 Correct 67 ms 71088 KB Output is correct
4 Correct 72 ms 71092 KB Output is correct
5 Correct 70 ms 71092 KB Output is correct
6 Correct 67 ms 71184 KB Output is correct
7 Correct 72 ms 71184 KB Output is correct
8 Correct 66 ms 71184 KB Output is correct
9 Correct 65 ms 71184 KB Output is correct
10 Correct 68 ms 71184 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 71184 KB Output is correct
2 Correct 319 ms 71772 KB Output is correct
3 Correct 74 ms 71772 KB Output is correct
4 Correct 109 ms 71772 KB Output is correct
5 Correct 169 ms 71880 KB Output is correct
6 Correct 82 ms 71880 KB Output is correct
7 Correct 249 ms 72120 KB Output is correct
8 Correct 171 ms 72136 KB Output is correct
9 Correct 70 ms 72136 KB Output is correct
10 Correct 74 ms 72136 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 75888 KB Output is correct
2 Execution timed out 1083 ms 86660 KB Time limit exceeded
3 Halted 0 ms 0 KB -