Submission #868793

#	Time	Username	Problem	Language	Result	Execution time	Memory
868793		HuyQuang_re_Zero	Jousting tournament (IOI12_tournament)	C++14	0 / 100	97 ms	80968 KiB

tournament

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 500005
using namespace std;
struct International_Olympiad_in_Informatics
{
    struct Interval_Tree
    {
        int st[4*N];
        void build(int id,int l,int r)
        {
            if(l==r) { st[id]=1; return ; }
            int mid=(l+r)>>1;
            build(id*2,l,mid); build(id*2+1,mid+1,r);
            st[id]=st[id*2]+st[id*2+1];
        }
        int Find(int id,int l,int r,int k)
        {
            if(l==r) return l;
            int mid=(l+r)>>1;
            if(k<=st[id*2]) return Find(id*2,l,mid,k);
            return Find(id*2+1,mid+1,r,k-st[id*2]);
        }
        void update(int id,int l,int r,int u)
        {
            if(u<l || u>r) return ;
            if(l==r) { st[id]=0; return ; }
            int mid=(l+r)>>1;
            update(id*2,l,mid,u); update(id*2+1,mid+1,r,u);
            st[id]=st[id*2]+st[id*2+1];
        }
    } IT;

    struct Sparse_Table
    {
        int bin[N],rmq[N][21];
        void add(int i,int k)
        {
            bin[i]=trunc(log2(i));
            rmq[i][0]=k;
            for(int j=1;j<=bin[i];j++)
                rmq[i][j]=max(rmq[i][j-1],rmq[i-(1<<(j-1))][j-1]);
        }
        int get(int l,int r)
        {
            if(l>r) return 0;
            int k=bin[r-l+1];
            return max(rmq[r][k],rmq[l+(1<<k)-1][k]);
        }
    } RMQ;



    struct pt { int k,type,pos; } seg[N];
    int l[N],r[N],len[N],i,j,q,m,f[N],ok[N],p[N],res,pos,u;
    vector <int> a[N];

    void DFS(int u)
    {
      //  cerr<<u<<" "<<f[u]<<'\n';
        if(ok[u]) f[u]=f[p[u]]+1; else f[u]=0;
        if(len[u]==1 && (res<f[u] || (res==f[u] && pos>l[u])))
            res=f[u],pos=l[u];
        for(int v:a[u]) DFS(v);
    }
    int Work(int n,int q,int my_point,int point[],int L_battle[],int R_battle[])
    {
        IT.build(1,1,n);
        for(i=1;i<=q;i++)
        {
            int mi,ma;
            if(L_battle[i]==1) mi=1; else mi=IT.Find(1,1,n,L_battle[i]-1)+1;
            ma=IT.Find(1,1,n,R_battle[i]);
            for(j=L_battle[i];j<R_battle[i];j++)
            {
                int u=IT.Find(1,1,n,L_battle[i]);
                IT.update(1,1,n,u);
            }
            seg[++m]={ mi,0,i };
            seg[++m]={ ma,1,i };
            len[i]=ma-mi+1;
            l[i]=mi; r[i]=ma;
        }
        for(i=1;i<=n;i++)
        {
            q++;
            l[q]=r[q]=i; len[q]=1;
            seg[++m]={ i,0,q };
            seg[++m]={ i,1,q };
        }

        for(i=1;i<n;i++) RMQ.add(i,point[i]);

        sort(seg+1,seg+m+1,[&](pt a,pt b)
             {
                if(a.k!=b.k) return a.k<b.k;
                if(a.type!=b.type) return a.type<b.type;
                if(a.type==0) return len[a.pos]>len[b.pos];
                return len[a.pos]<len[b.pos];
             });
        stack <pt> st;
        for(i=1;i<=m;i++)
            if(seg[i].type==0) st.push(seg[i]);
            else
            {
                int u=seg[i].pos;
                ok[u]=(RMQ.get(l[u],r[u]-1)<my_point);
                while(st.top().pos!=seg[i].pos)
                {
                    int v=st.top().pos;
                    a[u].push_back(v);
                    p[v]=u;
                    st.pop();
                }

            }
        vector <int> vec;
        for(i=1;i<=q;i++) vec.push_back(i);
        sort(vec.begin(),vec.end(),[&](int i,int j){ return len[i]>len[j]; });
        res=0; pos=1;
        for(int u:vec)
        {
            if(ok[u]) f[u]=f[p[u]]+1; else f[u]=0;
            if(len[u]==1 && (res<f[u] || (res==f[u] && pos>l[u])))
                res=f[u],pos=l[u];
        }
        return pos;
    }
} IOI;

int GetBestPosition(int n,int q,int my_point,int point[],int L_battle[],int R_battle[])
{
    my_point++;
    for(int i=n-1;i>=1;i--) point[i]=point[i-1],point[i]++;
    for(int i=q;i>=1;i--)
    {
        L_battle[i]=L_battle[i-1]; L_battle[i]++;
        R_battle[i]=R_battle[i-1]; R_battle[i]++;
    }
    return IOI.Work(n,q,my_point,point,L_battle,R_battle)-1;
}
/*
int n,q,my_point,point[N],L_battle[N],R_battle[N],i;
int main()
{
    freopen("tournament.inp","r",stdin);
    freopen("tournament.out","w",stdout);
    cin>>n>>q>>my_point;
    for(i=0;i<n-1;i++) cin>>point[i];
    for(i=0;i<q;i++) cin>>L_battle[i]>>R_battle[i];
    cout<<GetBestPosition(n,q,my_point,point,L_battle,R_battle);
}

*/

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