Submission #241348

#	Time	Username	Problem	Language	Result	Execution time	Memory
241348		kshitij_sodani	Jousting tournament (IOI12_tournament)	C++17	0 / 100	255 ms	3532 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];
			}
		}
	}
	return ind;
}
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;
		}
	}
	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]=min(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;
	if(n==1){
		while(true){
			continue;
		}
	}
	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);

	for(int j=0;j<c;j++){
		aa[j]=find2(ss[j]+1);

		bb[j]=find(tt[j]+1);
		for(int i=ss[j]+1;i<=tt[j];i++){
			u(i+1,-1);
		}
		cout<<aa[j]<<","<<bb[j]<<endl;
		aa[j]-=1;
		bb[j]-=2;
	//	cout<<aa[j]<<","<<bb[j]<<endl;
	//	cout<<endl;
		if(query(0,0,n-2,aa[j],bb[j])<r){
		//	cout<<j<<endl;
			u2(aa[j]+1,1);
			u2(bb[j]+3,-1);
			cout<<aa[j]+1<<"::"<<bb[j]+2<<endl;
		}
	}
	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