oj.uz

Submission #31152

# Submission time Handle Problem Language Result Execution time Memory
31152 2017-08-11T17:02:26 Z skykhs3 Jousting tournament (IOI12_tournament) C++11
100 / 100
 129 ms 6680 KB 
#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

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.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5932 KB Output is correct
2 Correct 96 ms 6680 KB Output is correct
3 Correct 29 ms 5928 KB Output is correct
4 Correct 99 ms 6680 KB Output is correct
5 Correct 103 ms 6644 KB Output is correct
6 Correct 83 ms 6416 KB Output is correct
7 Correct 129 ms 6680 KB Output is correct
8 Correct 103 ms 6680 KB Output is correct
9 Correct 13 ms 5928 KB Output is correct
10 Correct 19 ms 5928 KB Output is correct