Submission #579508

#	Time	Username	Problem	Language	Result	Execution time	Memory
579508		ansol4328	Jousting tournament (IOI12_tournament)	C++17	100 / 100	232 ms	38104 KiB

tournament

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> P;

struct PST{
    struct Node{
        int sum, L, R;
    };
    vector<Node> tree;
    vector<int> root;
    int h, cnt, base;
    PST(int a, int b, int rn){
        h=cnt=base=1;
        while(base<a) base<<=1, h++;
        int tmp=base*2+h*b+5;
        tree.resize(tmp);
        root.resize(rn+5);
        root[0]=setup(1,base);
    }
    int setup(int ns, int nf){
        int k=cnt++;
        tree[k].sum=0;
        if(ns<nf){
            int mid=(ns+nf)>>1;
            tree[k].L=setup(ns,mid);
            tree[k].R=setup(mid+1,nf);
        }
        return k;
    }
    void update_Kth_tree(int k, int idx=-1, int v=-1){
        if(root[k]==0) root[k]=root[k-1];
        if(idx!=-1) root[k]=make(root[k],idx,v);
    }
    int make(int bef, int idx, int v, int ns=1, int nf=-1){
        if(nf==-1) nf=base;
        if(nf<idx || idx<ns) return bef;
        int k=cnt++;
        if(ns==nf) tree[k].sum=tree[bef].sum+v;
        else{
            int mid=(ns+nf)>>1;
            tree[k].L=make(tree[bef].L,idx,v,ns,mid);
            tree[k].R=make(tree[bef].R,idx,v,mid+1,nf);
            tree[k].sum=tree[tree[k].L].sum+tree[tree[k].R].sum;
        }
        return k;
    }
    int qry(int num, int st, int fn, int ns=1, int nf=-1){
        if(nf==-1) nf=base;
        if(nf<st || fn<ns) return 0;
        if(st<=ns && nf<=fn) return tree[num].sum;
        int mid=(ns+nf)>>1;
        return qry(tree[num].L,st,fn,ns,mid)+qry(tree[num].R,st,fn,mid+1,nf);
    }
};

int n, q, val, m[100005];
P qry[100005];

void fastio(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
}

int GetBestPosition(int N, int C, int V, int *K, int *S, int *E){
    n=N; q=C, val=V;
    vector<int> id; id.pb(0);
    for(int i=0 ; i<n-1 ; i++){
        m[i]=K[i];
        if(m[i]>val) id.pb(i+1);
    }
    id.pb(n);
// 1. re-indexing the segment by using pbds ordered set
    ordered_set L, R;
    for(int i=0 ; i<n ; i++) L.insert(i), R.insert(i);
    for(int i=1 ; i<=q ; i++){
        int x=S[i-1], y=E[i-1];
        int t=y-x;
        auto li=L.find_by_order(x);
        qry[i].fi=*li;
        li++;
        for(int j=0 ; j<t ; j++){
            auto tmp=li; li++;
            L.erase(tmp);
        }
        auto ri=R.find_by_order(y);
        qry[i].se=*ri;
        ri--;
        for(int j=0 ; j<t ; j++){
            auto tmp=ri; ri--;
            R.erase(tmp);
        }
    }
// 2. insert every segment to sum PST [l,r] -> insert +1 at (r+1)th index of (l+1)th tree
    sort(qry+1,qry+1+q);
    PST pst(n,q,n);
    int cur=1;
    for(int i=1 ; i<=q ; i++){
        while(cur<qry[i].fi+1) pst.update_Kth_tree(cur++);
        if(cur==qry[i].fi+1) pst.update_Kth_tree(cur,qry[i].se+1,1);
    }
// 3. for every end point of devided segment, get # of wins from PST and calculate best position
    int mx=0, ans=0;
    for(int i=0, sz=(int)id.size()-1 ; i<sz ; i++){
        int st=id[i]+1, fn=id[i+1];
        for(int j=st ; j<=fn ; j++){
            int ret=pst.qry(pst.root[j],j,fn)-pst.qry(pst.root[st-1],j,fn);
            if(mx<ret) mx=ret, ans=j-1;
        }
    }
    return ans;
}

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