Submission #31186

#	Time	Username	Problem	Language	Result	Execution time	Memory
31186		14kg	Jousting tournament (IOI12_tournament)	C++11	100 / 100	109 ms	9288 KiB

tournament

#include <algorithm>
#include <stdio.h>
#include <stack>
#define N 100001
#define NN 131072
#define INF 999999999

using namespace std;
typedef pair<pair<int,int>,int> ppi;
int n, m, knight, p[N];
int nn, tree[NN*2], tree2[NN*2], tree_max[NN*2];
pair<int,int> match[N];
ppi d[N];
stack<pair<int,int> > S;

bool cmp(ppi x, ppi y){
    if(x.first.first!=y.first.first) return x.first.first<y.first.first;
    return x.first.second>y.first.second;
}
int max2(int x, int y){ return x>y?x:y; }

int get_w(int lev, int l, int r, int num){
    int mid=(l+r)/2;
    if(l==r && num==tree[lev]) return l;
    if(l==r) return 0;

   // printf("%d(%d - %d - %d) > %d %d / [%d]%d\n",lev,l,mid,r,tree[lev*2],tree[lev*2+1],tree2[lev*2],num);
    if(num>tree2[lev*2]) return get_w(lev*2+1,mid+1,r,num-tree[lev*2]);
    else return get_w(lev*2,l,mid,num);
}
void Update(int x){
    tree[x]=tree[x*2]+tree[x*2+1];
    tree2[x]=max2(tree2[x*2],tree[x*2]+tree2[x*2+1]);
    if(x>1) Update(x/2);
}

int f(int lev, int l, int r, int x, int y){
    int mid=(l+r)/2;
    if(x<=l && r<=y) return tree_max[lev];
    if(r<x || y<l) return 0;
    return max2(f(lev*2,l,mid,x,y),f(lev*2+1,mid+1,r,x,y));
}

int GetBestPosition(int _n, int _m, int _knight, int *_p, int *_in1, int *_in2){
    n=_n, m=_m, knight=_knight;
    for(int i=0; i<n-1; i++) p[i+1]=_p[i];
    for(int i=0; i<m; i++) match[i+1]=make_pair(_in1[i]+1,_in2[i]+1);

    for(nn=1; nn<n; nn*=2);
    for(int i=1; i<=n; i++){
        tree2[i+nn-1]=tree[i+nn-1]=1;
        tree_max[i+nn-1]=p[i];
    }
    for(int i=nn-1; i>=1; i--){
        tree2[i]=tree[i]=tree[i*2]+tree[i*2+1];
        tree_max[i]=max2(tree_max[i*2],tree_max[i*2+1]);
    }

    for(int i=1; i<=m; i++){
        if(match[i].first==1) d[i].first.first=1;
        else d[i].first.first=get_w(1,1,nn,match[i].first-1)+1;

        d[i].first.second=get_w(1,1,nn,match[i].second);
        d[i].second=i;

        tree[d[i].first.first+nn-1]-=match[i].second-match[i].first;
        tree2[d[i].first.first+nn-1]-=match[i].second-match[i].first;
        Update((d[i].first.first+nn-1)/2);
     //   printf(">>%d %d\n",d[i].first,d[i].second);
     //   break;
    } sort(d+1,d+m+1,cmp);

    int MAX=-1, out, w=1, temp;
    S.push(make_pair(INF,0));
    for(int i=1; i<=n; i++){
        while(S.top().first<i) S.pop();
        while(w<=m && d[w].first.first<=i){
            temp=f(1,1,nn,d[w].first.first,d[w].first.second-1);
            if(temp<knight) S.push(make_pair(d[w].first.second,S.top().second+1));
            else S.push(make_pair(d[w].first.second,0));
            w++;
        }
        if(MAX<S.top().second) MAX=S.top().second, out=i;
    } return out-1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:84:18: warning: 'out' may be used uninitialized in this function [-Wmaybe-uninitialized]
     } return out-1;
                  ^

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