Submission #241356

#	Time	Username	Problem	Language	Result	Execution time	Memory
241356		kshitij_sodani	Jousting tournament (IOI12_tournament)	C++17	0 / 100	1079 ms	2092 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;
	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;
		for(int i=aa[j]+1;i<=bb[j];i++){
			u(i,-1);
		}
		
	//	cout<<aa[j]<<",,"<<bb[j]<<endl;
		aa[j]-=1;
		bb[j]-=1;
	//	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++){
		if(arr[i]==maa){
			return i;
		}
	}

	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
*/

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