Submission #1131816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131816		t9unkubj	Jousting tournament (IOI12_tournament)	C++20	0 / 100	0 ms	324 KiB

tournament

#ifdef t9unkubj


#define _GLIBCXX_DEBUG
#include"debug.cpp"

//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
template<class monoid>
struct segtree{
    int n;
    vector<monoid>node;
    static monoid e(){
        return monoid::e();
    }
    static monoid op(monoid a,monoid b){
        return monoid::op(a,b);
    }

    segtree(){}
    segtree(int n):n(n),node(n*2,e()){
        assert(0<=n);
    }
    void set(int i,monoid x){
        assert(0<=i&&i<n);
        node[i+=n]=x;
        while(i>>=1)node[i]=op(node[i<<1],node[i<<1|1]);
    }
    monoid prod(int l,int r) const {
        assert(0<=l&&l<=r&&r<=n);
        l+=n,r+=n;
        monoid sml=e(),smr=e();
        while(l<r){
            if(l&1)sml=op(sml,node[l++]);
            if(r&1)smr=op(node[--r],smr);
            l>>=1,r>>=1;
        }
        return op(sml,smr);
    }
    monoid get(int i){
        assert(0<=i&&i<=n);
		return node[i+n];
	}
    //return max val s.t. f([L,val))) = true
    template<class F>
    int max_right(int L,const F&f) const {
        assert(f(e()));
        int l=n+L;   
        int w=1;
        monoid ansL=e();
        for(;L+w<=n;l>>=1,w<<=1){
            if(l&1){
                if(!(f(op(ansL,node[l]))))break;
                ansL=op(ansL,node[l++]);
                L+=w;
            }
        }
        while(l<<=1,w>>=1){
            if(L+w<=n&&f(op(ansL,node[l]))){
                ansL=op(ansL,node[l++]);
                L+=w;
            }
        }
        return L;
    }
    //return min val s.t. f([val,R)) = true
    template<class F>
    int min_left(int R,const F&f) const {
        assert(f(e()));
        int r=n+R;   
        int w=1;
        monoid ansR=e();
        for(;R-w>=0;r>>=1,w<<=1){
            if(r&1){
                if(!(f(op(node[r-1],ansR))))break;
                ansR=op(node[--r],ansR);
                R-=w;
            }
        }
        while(r<<=1,w>>=1){
            if(R-w>=0&&f(op(node[r-1],ansR))){
                ansR=op(node[--r],ansR);
                R-=w;
            }
        }
        return R;
    }
};

template<class T,auto op,int extra>
struct base_dsu{
        vector<int>par;
        vector<T>data;
        base_dsu(int n):par(n,-1){
            static_assert(!extra,"e is needed");
        }
        base_dsu(int n,T e):par(n,-1),data(n,e){}
        T& operator[](int i){
            static_assert(extra,"No data");
            return data[leader(i)];
        }
        int root(int x){
            if(par[x]<0)return x;
            else return par[x]=root(par[x]);
        }
        bool same(int x,int y){
            return root(x)==root(y);
        }
        bool merge(int x,int y){
            x=root(x);
            y=root(y);
            if(x==y)return false;
            if(par[x]>par[y])swap(x,y);
            par[x]+=par[y];
            par[y]=x;
            if(extra){
                data[x]=op(data[y],data[x]);
            }
            return true;
        }
        int size(int x){
            return -par[root(x)];
        }
        int leader(int x){
            return root(x);
        }

};
int tf323(int a,int b){return a;}
using dsu=base_dsu<int,tf323,0>;
template<class T,auto op>
using extra_dsu=base_dsu<T,op,1>;
struct mono{
    int val;
    static mono op(mono a,mono b){
        return mono{a.val+b.val};
    }
    
    static mono add(mono a,int b){
        return mono{a.val+b};
    }
    static mono e(){
        return mono{0};
    }
};
struct mono2{
    int val;
    static mono2 op(mono2 a,mono2 b){
        return mono2{max(a.val,b.val)};
    }
    static mono2 e(){
        return mono2{0};
    }
};
pair<int,int>op(pair<int,int>a,pair<int,int>b){
    return pair<int,int>(min(a.first,b.first),max(a.second,b.second));
}
int solve(int n,int q,int p,vc<int>k,vc<int>l,vc<int>r){
    dbg(n,q,p,k,l,r);
    segtree<mono2>seg(n-1);
    rep(i,n-1)seg.set(i,mono2{k[i]});
    vc<int>tl(q),tr(q);
    {
        extra_dsu<pair<int,int>,op>dsu(n,{(int)1e9,(int)-1e9});
        rep(i,n)dsu[i]={i,i};
        set<int>ex;
        rep(i,n)ex.insert(i);
        segtree<mono>seg(n);
        rep(i,n)seg.set(i,mono{1});
        rep(i,q){
            int S=seg.prod(0,n).val;
            int LEFT=seg.max_right(0,[&](auto a){
                return a.val<l[i]+1;
            });

            int RIGHT=seg.min_left(n,[&](auto a){
                return a.val<(S-r[i]);
            })-1;
            tl[i]=dsu[LEFT].first,tr[i]=dsu[RIGHT].second;
            dsu.merge(LEFT,RIGHT);
            auto itr=ex.lower_bound(LEFT);
            while(1){
                if(itr==ex.end()||*itr>=r[i])break;
                dsu.merge(*itr,LEFT);
                seg.set(*itr,mono{0});
                ex.erase(itr);
                itr=ex.lower_bound(LEFT);
            }
        }
    }
    dbg(tl,tr);
    segtree<mono>win(n);
    set<int>lose;
    lose.insert(n);
    pair<int,int>res{0,0};
    vvc<pair<int,int>>query(n+1);
    rep(i,q){
        query[tl[i]].push_back({i,1});
        query[tr[i]+1].push_back({i,-1});
    }
    rep(i,n){
        for(auto&[idx,t]:query[i]){
            dbg(i,idx);
            if(t==1){
                auto R=seg.prod(tl[idx],tr[idx]-1);
                if(R.val<p){
                    win.set(idx,mono{1});
                }else{
                    lose.insert(idx);
                }
            }else{
                auto R=seg.prod(tl[idx],tr[idx]-1);
                if(R.val<p){
                    win.set(idx,mono{0});
                }else{
                    lose.erase(idx);
                }
            }
            dbg(lose);
        }
        chmax(res,pair<int,int>(win.prod(0,*lose.begin()).val,-i));
    }
    dbg(res);
    return -res.second;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    vc<int>k(N-1),l(C),r(C);
    rep(i,N-1)k[i]=K[i];
    rep(i,C)l[i]=S[i],r[i]=E[i];
    return solve(N,C,R,k,l,r);
}
namespace judge{
    void run(){
        int n,c,r;
        cin>>n>>c>>r;
        int k[n-1],s[c],e[c];
        rep(i,n-1)cin>>k[i];
        rep(i,c)cin>>s[i]>>e[i];
        cout<<GetBestPosition(n,c,r,k,s,e)<<"\n";
    }
};
//int main(){judge::run();}
//g++ env/tournament.cpp -D t9unkubj
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/

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