Submission #31152

#	Time	Username	Problem	Language	Result	Execution time	Memory
31152		skykhs3	Jousting tournament (IOI12_tournament)	C++11	100 / 100	129 ms	6680 KiB

tournament

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int N,C,R,nn,sum[MAXN],v,mx=-1;
int seg[MAXN*4],mxseg[MAXN*4];
int *K,*S,*E;
int query1(int lef,int rig,int lev,int x){
    if(x==0) return -1;
    if(lef==rig) return lef;
    else{
        int mid=lef+rig>>1;
        if(seg[lev*2]>=x) return query1(lef,mid,lev*2,x);
        else return query1(mid+1,rig,lev*2+1,x-seg[lev*2]);
    }
}
void query2(int lef,int rig,int lev,int s,int e){
    if(rig<s || e<lef) return;
    if(s<=lef && rig<=e) seg[lev]=0;
    else{
        int mid=(lef+rig)/2;
        query2(lef,mid,lev*2,s,e);
        query2(mid+1,rig,lev*2+1,s,e);
        seg[lev]=seg[lev*2]+seg[lev*2+1];
    }
}
int query3(int lef,int rig,int lev,int s,int e){
    if(rig<s || e<lef) return -1;
    if(s<=lef && rig<=e) return mxseg[lev];
    else{
        int mid=lef+rig>>1;
        return max(query3(lef,mid,lev*2,s,e),query3(mid+1,rig,lev*2+1,s,e));
    }
}
int GetBestPosition(int iN, int iC, int iR, int *iK, int *iS, int *iE)
{
    N=iN,C=iC,R=iR,K=iK,S=iS,E=iE;
    for(nn=1;nn<N;nn*=2);
    for(int i=0;i<N;i++) seg[i+nn]=1,mxseg[i+nn]=K[i];
    for(int i=nn-1;i>=1;i--) seg[i]=seg[i*2]+seg[i*2+1],mxseg[i]=max(mxseg[i*2],mxseg[i*2+1]);
    for(int i=0;i<C;i++){
        int p2=query1(0,nn-1,1,E[i]+1),p1=query1(0,nn-1,1,S[i])+1;
        query2(0,nn-1,1,p1,p2-1);
        if(query3(0,nn-1,1,p1,p2-1)<=R) sum[p1]++,sum[p2+1]--;
    }
    int st=0;
    for(int i=0;i<N;i++){
        st+=sum[i];
        if(mx<st){
            mx=st;
            v=i;
        }
    }
    return v;
}

Compilation message (stderr)

tournament.cpp: In function 'int query1(int, int, int, int)':
tournament.cpp:11:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=lef+rig>>1;
                    ^
tournament.cpp: In function 'int query3(int, int, int, int, int)':
tournament.cpp:30:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=lef+rig>>1;
                    ^

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