oj.uz

Submission #579508

# Submission time Handle Problem Language Result Execution time Memory
579508 2022-06-19T09:51:55 Z ansol4328 Jousting tournament (IOI12_tournament) C++17
100 / 100
 232 ms 38104 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 8 ms 2004 KB Output is correct
3 Correct 6 ms 852 KB Output is correct
4 Correct 8 ms 2004 KB Output is correct
5 Correct 7 ms 1864 KB Output is correct
6 Correct 8 ms 1620 KB Output is correct
7 Correct 8 ms 1876 KB Output is correct
8 Correct 7 ms 2004 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 9 ms 2004 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 14476 KB Output is correct
2 Correct 228 ms 38104 KB Output is correct
3 Correct 174 ms 11268 KB Output is correct
4 Correct 217 ms 37968 KB Output is correct
5 Correct 214 ms 36644 KB Output is correct
6 Correct 230 ms 29260 KB Output is correct
7 Correct 227 ms 37920 KB Output is correct
8 Correct 232 ms 38080 KB Output is correct
9 Correct 161 ms 11360 KB Output is correct
10 Correct 159 ms 11356 KB Output is correct