Submission #13522

#	Time	Username	Problem	Language	Result	Execution time	Memory
13522		pseudopodia	Jousting tournament (IOI12_tournament)	C++98	49 / 100	37 ms	25748 KiB

tournament

#include<stdio.h>
int n,r,p,t,realtrash;
struct dataa{
    int x,y;
}sit[1050100];
struct data{
    int x,y;
}b[500100];
struct dataaa{
    int x,y;
}ba[500100];
int bit[1050100],bitt[1050100],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