제출 #13517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13517		pseudopodia	마상시합 토너먼트 (IOI12_tournament)	C++98	49 / 100	41 ms	9344 KiB

tournament

#include<stdio.h>
int n,r,p,t,realtrash;
struct dataa{
	int x,y;
}sit[400100];
struct data{
	int x,y;
}b[100100];
struct dataaa{
	int x,y;
}ba[100100];
int bit[400100],bitt[400100],t1;
void gang(int x,int p,int ch){
	if(p>=t && p<t*2){
		if(sit[p].y==0) {if(ch==1) b[realtrash].x=p-t+1; else b[realtrash].y=p-t+1;}
		else {if(ch==1) b[realtrash].x=p-t+1; else b[realtrash].y=sit[p].y;}
		return;
	}
	if(sit[p*2].x>=x) gang(x,p*2,ch); else gang(x-sit[p*2].x,p*2+1,ch);
	return;
}
void rem(int x,int y,int s,int e,int p){
	if(e<x || y<s) return;
	if(x<=s && y>=e) {sit[p].x=0; return;}
	rem(x,y,s,(s+e)/2,p*2); rem(x,y,(s+e)/2+1,e,p*2+1); sit[p].x=sit[p*2].x+sit[p*2+1].x; return;
}
int maximum(int x,int y,int s,int e,int p){
	int a1,a2;
	if(e<x || y<s) return 0;
	if(x<=s && y>=e) return bit[p];
	a1=maximum(x,y,s,(s+e)/2,p*2);
	a2=maximum(x,y,(s+e)/2+1,e,p*2+1);
	if(a1>a2) return a1; else return a2;
}
int maxi(int x,int y)
{
	if(x>y) return x; 
	else return y;
}
void regist(int x,int y,int s,int e,int p){
	if(e<x || y<s) return;
	if(x<=s && y>=e) {bitt[p]++; return;}
	regist(x,y,s,(s+e)/2,p*2);
	regist(x,y,(s+e)/2+1,e,p*2+1);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	int i,j;
	n=N;
	r=C;
	p=R;
	t=1;
	while(t<n) t*=2;
	for(i=t;i<=t*2-1;i++) sit[i].x=1;
	for(i=t-1;i>=1;i--) sit[i].x=sit[i*2].x+sit[i*2+1].x;
	for(i=1;i<=r;i++){
		S[i-1]++;
		E[i-1]++;
		realtrash=i;
		gang(S[i-1],1,1);
		gang(E[i-1],1,2);
		rem(b[i].x+1,b[i].y,1,t,1);
		sit[t-1+b[i].x].y=b[i].y;
	}
	t=1;
	while(t<n-1) t*=2;
	for(i=t;i<=t*2-1;i++) bit[i]=K[i-t];
	for(i=t-1;i>=1;i--){
		bit[i]=maxi(bit[i*2],bit[i*2+1]);
	}
	int cntt;
	t1=1;
	while(t1<n) t1*=2;
	for(i=1;i<=r;i++){
		cntt=maximum(b[i].x,b[i].y-1,1,t,1);
		if(cntt<p) regist(b[i].x,b[i].y,1,t1,1);
	}
	for(i=1;i<t1;i++) {bitt[i*2]+=bitt[i]; bitt[i*2+1]+=bitt[i]; bitt[i]=0;}
	int maxx=-1,maxii=1;
	for(i=t1;i<t1*2;i++) {if(maxx<bitt[i]) {maxx=bitt[i]; maxii=i;}}
	return maxii-t1;
}

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