oj.uz

답안 #241359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241359 2020-06-24T05:37:21 Z kshitij_sodani 마상시합 토너먼트 (IOI12_tournament) C++17
100 / 100
 132 ms 11000 KB 
#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 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];
			}
		}
	}
	return ind+1;
	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++){
		int x=s2(i+1);
		if(x>maa){
			maa=x;
			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

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

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 10 ms 896 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 10 ms 896 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 7 ms 768 KB Output is correct
10 Correct 11 ms 896 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 4860 KB Output is correct
2 Correct 130 ms 10872 KB Output is correct
3 Correct 62 ms 8952 KB Output is correct
4 Correct 127 ms 11000 KB Output is correct
5 Correct 130 ms 10744 KB Output is correct
6 Correct 132 ms 10232 KB Output is correct
7 Correct 129 ms 11000 KB Output is correct
8 Correct 131 ms 11000 KB Output is correct
9 Correct 59 ms 8824 KB Output is correct
10 Correct 69 ms 8696 KB Output is correct