Submission #575929

#	Time	Username	Problem	Language	Result	Execution time	Memory
575929		ogibogi2004	Jousting tournament (IOI12_tournament)	C++14	100 / 100	643 ms	15676 KiB

tournament

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+6;
const int lg=18;
int par[MAXN][lg];
vector<int>g[MAXN];
int n;
bool not_leaf[MAXN];
struct BIT
{
    int fen[MAXN];
    int tree[4*MAXN];
    int lazy[4*MAXN];
    void push(int l,int r,int idx)
    {
        if(lazy[idx]==0)return;
        tree[idx]=0;
        if(l!=r)
        {
            lazy[idx*2]+=lazy[idx];
            lazy[idx*2+1]+=lazy[idx];
        }
        lazy[idx]=0;
    }
    void build(int l,int r,int idx)
    {
        tree[idx]=r-l+1;
        lazy[idx]=0;
        if(l==r)return;
        int mid=(l+r)/2;
        build(l,mid,idx*2);
        build(mid+1,r,idx*2+1);
    }
    void update(int l,int r,int idx,int ql,int qr)
    {
        push(l,r,idx);
        if(l>qr)return;
        if(r<ql)return;
        if(l>=ql&&r<=qr)
        {
            lazy[idx]=1;
            push(l,r,idx);
            return;
        }
        int mid=(l+r)/2;
        update(l,mid,idx*2,ql,qr);
        update(mid+1,r,idx*2+1,ql,qr);
        tree[idx]=tree[idx*2]+tree[idx*2+1];
    }
    int query(int l,int r,int idx,int ql,int qr)
    {
        if(ql>qr)return 0;
        push(l,r,idx);
        if(l>qr)return 0;
        if(r<ql)return 0;
        if(l>=ql&&r<=qr)return tree[idx];
        int mid=(l+r)/2;
        return query(l,mid,idx*2,ql,qr)+query(mid+1,r,idx*2+1,ql,qr);
    }
    int query(int idx)
    {
        return query(0,n-1,1,0,idx);
    }
    int get_start(int x)
    {
        int low=0,high=n-1,best,mid;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(query(mid)>=x)
            {
                best=mid;
                high=mid-1;
            }
            else low=mid+1;
        }
        return best;
    }
    int get_end(int x)
    {
        int low=0,high=n-1,best,mid;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(query(mid)<=x)
            {
                best=mid;
                low=mid+1;
            }
            else high=mid-1;
        }
        return best;
    }
}rp;
struct segment_tree
{
    int tree[4*MAXN];
    void build(int l,int r,int idx)
    {
        tree[idx]=MAXN;
        if(l!=r)
        {
            int mid=(l+r)/2;
            build(l,mid,idx*2);
            build(mid+1,r,idx*2+1);
        }
    }
    void update(int l,int r,int idx,int ql,int qr,int val)
    {
        if(l>qr)return;
        if(r<ql)return;
        if(l>=ql&&r<=qr)
        {
            tree[idx]=min(tree[idx],val);
            return;
        }
        int mid=(l+r)/2;
        update(l,mid,idx*2,ql,qr,val);
        update(mid+1,r,idx*2+1,ql,qr,val);
    }
    int query(int l,int r,int idx,int q)
    {
        //cout<<l<<" "<<r<<" "<<idx<<" "<<q<<endl;
        if(l>q)return MAXN;
        if(r<q)return MAXN;
        if(l==r)return tree[idx];
        int mid=(l+r)/2;
        return min(tree[idx],min(query(l,mid,idx*2,q),query(mid+1,r,idx*2+1,q)));
    }
}t;
struct segment_tree1
{
    int tree[4*MAXN];
    void update(int l,int r,int idx,int q,int val)
    {
        if(l>q)return;
        if(r<q)return;
        if(l==r)
        {
            tree[idx]=val;
            return;
        }
        int mid=(l+r)/2;
        update(l,mid,idx*2,q,val);
        update(mid+1,r,idx*2+1,q,val);
        tree[idx]=max(tree[idx*2],tree[idx*2+1]);
    }
    int query(int l,int r,int idx,int ql,int qr)
    {
        if(l>qr)return 0;
        if(r<ql)return 0;
        if(l>=ql&&r<=qr)return tree[idx];
        int mid=(l+r)/2;
        return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
    }
}t1;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    vector<pair<int,int> >real;
    //cout<<"?\n";
    rp.build(0,N-1,1);
    rp.update(0,N-1,1,0,0);
    //cout<<"?\n";
    for(int i=0;i<C;i++)
    {
        int s1=rp.get_start(S[i]);
        int e1=rp.get_end(E[i]);
        real.push_back({s1,e1});
        //cout<<s1<<" "<<e1<<endl;
        rp.update(0,N-1,1,s1+1,e1);
    }
    // down
    //cout<<"?\n";
    //reverse(real.begin(),real.end());
    t.build(0,N-1,1);
    t.update(0,N-1,1,real.back().first,real.back().second,real.size());
    par[real.size()][0]=0;
    for(int i=real.size()-2;i>=0;i--)
    {
        int br=t.query(0,N-1,1,real[i].first);
        par[i+1][0]=br;
        not_leaf[br]=1;
        t.update(0,N-1,1,real[i].first,real[i].second,i+1);
    }
    for(int step=1;step<lg;step++)
    {
        for(int i=1;i<=C;i++)
        {
            par[i][step]=par[par[i][step-1]][step-1];
        }
    }
    /*for(int i=1;i<=C;i++)
    {
        cout<<"^^ "<<i<<" "<<par[i][0]<<endl;
    }*/
    for(int i=1;i<N;i++)
    {
        t1.update(0,N-1,1,i,K[i-1]);
    }
    int ans=0,best=0;
    //down
    for(int i=0;i<N;i++)
    {
        //cout<<i<<":\n";
        //cout<<i<<endl;
        t1.update(0,N-1,1,i,0);
        int x=t.query(0,N-1,1,i);
        //
        int d=0;
        for(int j=lg-1;j>=0;j--)
        {
            //cout<<" "<<j<<endl;
            //cout<<"   "<<x<<" "<<j<<" "<<par[x][j]<<endl;
            if(par[x][j]==0)continue;
            int f=par[x][j]-1;
            //cout<<"     "<<real[f].first<<" "<<real[f].second<<" "<<t1.query(0,N-1,1,real[f].first,real[f].second)<<endl;
            if(t1.query(0,N-1,1,max(0,real[f].first),min(N-1,real[f].second))>=R)
            {
                continue;
            }
            x=par[x][j];

            d+=(1<<j);
        }
        if(t1.query(0,N-1,1,max(0,real[x-1].first),min(N-1,real[x-1].second))<R)d++;
        //cout<<"?\n";
        //cout<<i<<"   "<<d<<endl;
        if(d>ans)
        {
            ans=d;
            best=i;
        }
        if(i==N-1)continue;
        //cout<<"   -\n";
        t1.update(0,N-1,1,i,K[i]);
    }
    return best;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:172:18: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  172 |         rp.update(0,N-1,1,s1+1,e1);
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~
tournament.cpp:48:15: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |         update(l,mid,idx*2,ql,qr);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~
tournament.cpp:83:28: note: 'best' was declared here
   83 |         int low=0,high=n-1,best,mid;
      |                            ^~~~

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