Submission #241358

#	Time	Username	Problem	Language	Result	Execution time	Memory
241358		kshitij_sodani	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1083 ms	4732 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
//#include "tournament.h"

int tree[110001];
int aa[100001];
int bb[100001];
int n;
void u(int i,int j){
	while(i<110001){
		tree[i]+=j;
		i+=(i&-i);
	}
}
int s(int i){
	int su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
int find(int x){
/*	int ind=0;
	int su=0;
	for(int i=19;i>=0;i--){
		if((1<<i)+ind<=n){
			if(su+tree[ind+(1<<i)]<=x){
				ind+=(1<<i);
				su+=tree[ind];
			}
		}
	}*/
	int ind2=0;
	for(int i=0;i<n+1;i++){
		if(s(i)==x){
			ind2=i;
		}
	}
	return ind2;
}
int find2(int x){
	/*int ind=0;
	int su=0;
	for(int i=19;i>=0;i--){
		if((1<<i)+ind<=n){
			if(su+tree[ind+(1<<i)]<x){
				ind+=(1<<i);
				su+=tree[ind];
			}
		}
	}
	if(s(ind+1)!=x){
		while(true){
			continue;
		}
	}*/
	for(int i=0;i<n+1;i++){
		if(s(i)==x){
			return i;
			
		}
	}
	return 0;
	//return ind+1;
}
int tree2[110001];
void u2(int i,int j){
	while(i<110001){
		tree2[i]+=j;
		i+=(i&-i);
	}
}
int s2(int i){
	int su=0;
	while(i>0){
		su+=tree2[i];
		i-=(i&-i);
	}
	return su;
}
int tree3[400001];
int kk[100001];
void build(int no,int l,int r){
	if(l==r){
		tree3[no]=kk[l];
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree3[no]=max(tree3[no*2+1],tree3[no*2+2]);
	}
}
int query(int no,int l,int r,int aa,int bb){
	if(r<aa or bb<l){
		return 0;
	}
//	cout<<l<<':'<<r<<endl;
	if(aa<=l and r<=bb){
		return tree3[no];
	}
	int mid=(l+r)/2;
	return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int GetBestPosition(int nn, int c, int r, int k[], int ss[], int tt[]) {
	n=nn;

	for(int i=0;i<n;i++){
		u(i+1,1);
	}
	for(int i=0;i<n-1;i++){
		kk[i]=k[i];
	}
	build(0,0,n-2);
	int arr[n];
	for(int i=0;i<n;i++){
		arr[i]=0;

	}
	int maa=0;
	set<int> xx;
	for(int i=0;i<n;i++){
		xx.insert(i+1);
	}
	for(int j=0;j<c;j++){
		aa[j]=find2(ss[j]+1);

		bb[j]=find(tt[j]+1);
	//	cout<<s(aa[j])<<"::"<<s(bb[j])<<endl;
		/*for(int i=0;i<n+1;i++){
			cout<<s(i)<<"<";
		}
		cout<<endl;*/
	//	cout<<endl;
		auto yy=xx.upper_bound(aa[j]);
		vector<int> de;
		while(yy!=xx.end()){
			if(*yy<=bb[j]){
				u(*yy,-1);
				de.pb(*yy);
				yy++;
			}
			else{
				break;
			}
		}
		for(auto j:de){
			xx.erase(j);
		}
	/*	for(int i=aa[j]+1;i<=bb[j];i++){
			cout<<i<<endl;
			u(i,-1);
		}
	*/	
		
	//	cout<<aa[j]<<",,"<<bb[j]<<endl;
		aa[j]-=1;
		bb[j]-=1;
		if(query(0,0,n-2,aa[j],bb[j]-1)<r){
			u2(aa[j]+1,1);
			u2(bb[j]+2,-1);
//			cout<<j<<endl;
		}
	//	cout<<aa[j]<<","<<bb[j]<<endl;
		continue;
	//	int x=0;

		
	//	cout<<endl;
		int ma=0;
		for(int i=aa[j];i<=bb[j]-1;i++){
			ma=max(ma,kk[i]);
		}
	//	cout<<aa[j]<<','<<bb[j]<<endl;
		if(ma<r){
		//	cout<<j<<endl;
			for(int i=aa[j];i<=bb[j];i++){
				arr[i]+=1;
				maa=max(maa,arr[i]);
			}
		//	u2(aa[j]+1,1);
		//	u2(bb[j]+3,-1);
	//		cout<<aa[j]+1<<"::"<<bb[j]+2<<endl;
		}

	}

/*	for(int i=0;i<n;i++){
		int co=0;
		for(int j=0;j<c;j++){
			int ma=0;
			for(int ko=aa[j];ko<=bb[j];ko++){
				if(ko<i){
					ma=max(ma,kk[ko]);
				}
				else{
					if(ko>i){
						ma=max(ma,kk[ko-1]);
					}
				}
			}
			if(ma<r and i>=aa[j] and i<=bb[j]){
				co+=1;
			}
		}
		arr[i]=co;
		//cout<<i<<"::"<<co<<endl;
		maa=max(maa,co);

	}*/
	maa=-1;
	int fin=0;
	for(int i=0;i<n;i++){
		if(s2(i+1)>maa){
			maa=s2(i+1);
			fin=i;
		}
	}
return fin;
	int ans=0;
	for(int i=0;i<n;i++){
		if(arr[i]==maa){
			return i;
		}
	}
	return 0;


	int mi=-1;
	int ind=0;
	for(int i=0;i<n;i++){
		int x=s2(i+1);
	//	cout<<i<<"::"<<x<<","<<ind<<endl;
		if(x>mi){
			mi=x;
			ind=i;
		}
	}


	return ind;
}

/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:227:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans=0;
      ^~~

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