Submission #966130

#	Time	Username	Problem	Language	Result	Execution time	Memory
966130		hirayuu_oj	Jousting tournament (IOI12_tournament)	C++17	100 / 100	192 ms	7768 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

template<class S,auto op,auto e>
struct SegmentTree{
    int size;
    vector<S> tree;
    SegmentTree(int sz){
        size=sz;
        tree.resize(size*2);
        rep(i,size*2)tree[i]=e();
    }
    void set(int pos,S val){
        pos+=size;
        tree[pos]=val;
        pos/=2;
        while(pos>0){
            tree[pos]=op(tree[pos*2],tree[pos*2+1]);
            pos/=2;
        }
    }
    S get(int pos){
        return tree[pos+size];
    }
    S prod(int lf,int ri){
        lf+=size;
        ri+=size;
        S ret_lf=e();
        S ret_ri=e();
        while(lf<ri){
            if(lf%2==1){
                ret_lf=op(ret_lf,tree[lf]);
                lf++;
            }
            if(ri%2==1){
                ri--;
                ret_ri=op(tree[ri],ret_ri);
            }
            lf/=2;
            ri/=2;
        }
        return op(ret_lf,ret_ri);
    }
};

using T=pair<int,int>;
T op(T x,T y){
    return {x.first+y.first,max(x.second,x.first+y.second)};
}
T e(){
    return {0,0};
}
T add(T x,T y){
    return {x.first+y.first,max(0,x.second+y.second)};
}
int ma(int x,int y){
    return max(x,y);
}
int me(){
    return -1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    SegmentTree<T, op, e> seg(N),seg2(N);
    SegmentTree<int, ma, me> night(N-1);
    rep(i,N){
        seg.set(i,{1,1});
        seg2.set(i,{1,1});
    }
    rep(i,N-1){
        night.set(i,K[i]);
    }
    vector<int> ans(N+1,0);
    rep(i,C){
        int s=S[i],e=E[i]+1;
        int ok=N,ng=-1;
        while(ok-ng>1){
            int mid=(ok+ng)/2;
            if(seg2.prod(0,mid).second>s){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        int lf=ok-1;
        ok=N;
        ng=-1;
        while(ok-ng>1){
            int mid=(ok+ng)/2;
            if(seg.prod(0,mid).second>e-1){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        int ri=ok;
        seg.set(lf,add(seg.get(lf),{-e+s+1,-e+s+1}));
        seg2.set(lf+1,add(seg2.get(lf+1),{-e+s+1,-e+s+1}));
        if(night.prod(lf,ri-1)<R){
            ans[lf]++;
            ans[ri]--;
        }
    }
    int fin=ans[0];
    int pos=0;
    rep(i,N-1){
        ans[i+1]+=ans[i];
        if(fin<ans[i+1]){
            fin=ans[i+1];
            pos=i+1;
        }
    }

    return pos;

}

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