oj.uz

Submission #13520

# Submission time Handle Problem Language Result Execution time Memory
13520 2015-02-22T14:34:18 Z pseudopodia Jousting tournament (IOI12_tournament) C++
49 / 100
 31 ms 14028 KB 
#include<stdio.h>
int n,r,p,t,realtrash;
struct dataa{
	int x,y;
}sit[550100];
struct data{
	int x,y;
}b[250100];
struct dataaa{
	int x,y;
}ba[250100];
int bit[550100],bitt[550100],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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13588 KB Output is correct
2 Correct 0 ms 13588 KB Output is correct
3 Correct 1 ms 13588 KB Output is correct
4 Correct 0 ms 13588 KB Output is correct
5 Correct 0 ms 13588 KB Output is correct
6 Correct 1 ms 13588 KB Output is correct
7 Correct 0 ms 13588 KB Output is correct
8 Correct 1 ms 13588 KB Output is correct
9 Correct 0 ms 13588 KB Output is correct
10 Correct 0 ms 13588 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13588 KB Output is correct
2 Correct 0 ms 13588 KB Output is correct
3 Correct 0 ms 13588 KB Output is correct
4 Correct 7 ms 13588 KB Output is correct
5 Correct 6 ms 13588 KB Output is correct
6 Correct 0 ms 13588 KB Output is correct
7 Correct 7 ms 13588 KB Output is correct
8 Correct 0 ms 13588 KB Output is correct
9 Correct 0 ms 13588 KB Output is correct
10 Correct 7 ms 13588 KB Output is correct

Subtask #3
0.0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 14028 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -