Submission #1131821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131821		t9unkubj	Jousting tournament (IOI12_tournament)	C++20	17 / 100	1095 ms	584 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 brute(int n,int q,int p,vc<int>k,vc<int>l,vc<int>r){
    pair<int,int>res{-1,-1};
    rep(i,n){
        int t=0;
        auto nk=k;
        nk.insert(nk.begin()+i,p);
        rep(j,q){
            int M=*max_element(nk.begin()+l[j],nk.begin()+r[j]+1);
            if(M==p)t++;
            int now=l[j];
            rep(s,r[j]-l[j]){
                if(nk[now]==M){
                    now++;
                }
                nk.erase(nk.begin()+now);
            }
        } 
        chmax(res,pair<int,int>{t,-i});
    }
    return -res.second;
}
int solve(int n,int q,int p,vc<int>k,vc<int>l,vc<int>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);
            }
        }
    }
    segtree<mono>win(q);
    set<int>lose;
    lose.insert(q);
    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]){
            if(t==1){
                auto R=seg.prod(tl[idx],tr[idx]);
                if(R.val<p){
                    win.set(idx,mono{1});
                }else{
                    lose.insert(idx);
                }
            }else{
                auto R=seg.prod(tl[idx],tr[idx]);
                if(R.val<p){
                    win.set(idx,mono{0});
                }else{
                    lose.erase(idx);
                }
            }
        }
        chmax(res,pair<int,int>(win.prod(0,*lose.begin()).val,-i));
    }
    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 brute(N,C,R,k,l,r);
}
mt19937 mt;
namespace judge{
    void check(){
        int n=5,q=mt()%n+1,p=mt()%n;
        vc<int>k(n-1),l(q),r(q);
        rep(i,n-1){
            k[i]=mt()%n;
        }        
        rep(i,q)l[i]=mt()%n,r[i]=mt()%n;
        set<int>st;
        st.insert(p);
        rep(i,n-1)st.insert(k[i]);
        if(st.size()!=n){
            return;
        }
        int seg=n-1;
        rep(i,q){
            if(seg<r[i])return;
            seg-=r[i]-l[i];
            if(l[i]>=r[i])return;
        }
        if(solve(n,q,p,k,l,r)!=brute(n,q,p,k,l,r)){
            dbg(n,q,p,k,l,r);
            dbg(solve(n,q,p,k,l,r));
            dbg(brute(n,q,p,k,l,r));
            assert(0);
        }
        dbg("OK"s);
    }
    void f(){
        while(1)check();
    }
    void run(){
        int n,c,r;
        cin>>n>>c>>r;
        vc<int>k(n-1),s(c),e(c);
        rep(i,n-1)cin>>k[i];
        rep(i,c)cin>>s[i]>>e[i];
        cout<<brute(n,c,r,k,s,e)<<"\n";
    }
};
//int main(){judge::f();}
//g++ env/tournament.cpp -D t9unkubj
/*
5 3 3
1 0 2 4 
1 3
0 1
0 1
*/

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