Submission #71576

#	Time	Username	Problem	Language	Result	Execution time	Memory
71576		MANcity	Jousting tournament (IOI12_tournament)	C++14	100 / 100	652 ms	44452 KiB

tournament

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int N;
int K[100002];
int gum[4*100002];
int color[4*100002];
int push(int v,int l,int r)
{
    if(color[v]!=-1)
    {
        color[2*v]=color[v];
        color[2*v+1]=color[v];
        color[v]=-1;
        int m=(l+r)/2;
        gum[2*v]=color[2*v]*(m-l+1);
        gum[2*v+1]=color[2*v+1]*(r-m);
    }
}
void update(int left,int right,int l,int r,int v,int val)
{
    if(l>r)
        return;
    if(left==l && right==r)
    {
        gum[v]=(right-left+1)*(val);
        color[v]=val;
    }
    else
    {
        int m=(left+right)/2;
        push(v,left,right);
        update(left,m,l,min(r,m),2*v,val);
        update(m+1,right,max(l,m+1),r,2*v+1,val);
        gum[v]=(gum[2*v]+gum[2*v+1]);
    }
}
int get(int left,int right,int l,int r,int v)
{
    if(l>r)
        return 0;
    if(left==l && right==r)
        return gum[v];
    int m=(left+right)/2;
    push(v,left,right);
    int A=get(left,m,l,min(r,m),2*v);
    int B=get(m+1,right,max(l,m+1),r,2*v+1);
    return (A+B);
}
int bin_1(int T)
{
    int l=0;
    int r=(N-1);
    while(1)
    {
        if(l==r)
            return l;
        int m=(l+r)/2;
        if(get(0,N-1,0,m,1)>=T)
            r=m;
        else
            l=(m+1);
    }
}
int bin_2(int T)
{
    int l=0;
    int r=(N-1);
    while(1)
    {
        if(l==r)
            return l;
        int m=(l+r+1)/2;
        if(get(0,N-1,0,m,1)>T)
            r=m-1;
        else
            l=m;
    }
}
vector<vector<int> > G(100002);
int leftNod[100002];
int rightNod[100002];
int pos[100002];
int up[100002][25];
int tin[100002];
int tout[100002];
int height[100002];
int timer=0;
bool upper(int a,int b)
{
    if(tin[a]<=tin[b] && tout[a]>=tout[b])
        return 1;
    return 0;
}
int lca(int a,int b)
{
    if(upper(a,b)) return a;
    if(upper(b,a)) return b;
    for(int i=22;i>=0;i--)
    {
        if(up[a][i]!=-1 && !upper(up[a][i],b))
        {
            //cout<<a<<" "<<i<<endl;
            a=up[a][i];
        }
    }
    return up[a][0];
}
void dfs(int v,int p)
{
    if(p!=-1)
        height[v]=height[p]+1;
    //cout<<v<<" "<<height[v]<<endl;
    tin[v]=++timer;
    up[v][0]=p;
    for1(i,22)
    {
        if(up[v][i-1]!=-1)
            up[v][i]=up[up[v][i-1]][i-1];
        else
            up[v][i]=-1;
    }
    for0(i,G[v].size()-1)
    {
        int to=G[v][i];
        if(to!=p)
            dfs(to,v);
    }
    tout[v]=++timer;
}
int mec_dzax[100002];
int mec_aj[100002];
int GetBestPosition(int N_0, int C, int R, int *K_0, int *S, int *E) {
    N=N_0;
    update(0,N-1,0,N-1,1,1);
    for0(i,N-2)
        K[i]=K_0[i];
    vector<vector<int> > begi(100002);
    vector<vector<int> > endi(100002);
    //cout<<endl;
    for0(i,C-1)
    {
        int posL=S[i];
        int posR=E[i];
        int pos_1=bin_1(posL+1);
        int pos_2=bin_2(posR+1);
        update(0,N-1,pos_1+1,pos_2,1,0);
        //cout<<i<<"    "<<pos_1<<" "<<pos_2<<endl;
        begi[pos_1].push_back(i);
        endi[pos_2].push_back(i);
    }
    //cout<<endl;
    //cout<<endl;
    stack<int> mystack;
    for0(i,N-1)
    {
        fr(j,begi[i].size()-1,0)
        {
            int to=begi[i][j];
            if(!mystack.empty())
            {
                int TOP=mystack.top();
                G[TOP].push_back(to);
            }
            mystack.push(to);
        }
        int TOP=mystack.top();
        pos[i]=TOP;
        for0(j,endi[i].size()-1)
            mystack.pop();
    }
    dfs(C-1,-1);
    /*for0(i,N-1)
    {
        cout<<i<<" "<<pos[i]<<endl;
    }*/
    mec_dzax[0]=-1;
    mec_aj[N-1]=-1;
    for1(i,N-1)
    {
        if(K[i-1]>R)
            mec_dzax[i]=i-1;
        else
            mec_dzax[i]=mec_dzax[i-1];
    }
    fr(i,N-2,0)
    {
        if(K[i]>R)
            mec_aj[i]=i;
        else
            mec_aj[i]=mec_aj[i+1];
    }
    //int ANS=0;
    vector<pair<int,int> > ANS;
    for0(i,N-1)
    {
        //cout<<i<<" "<<pos[i]<<" "<<height[pos[i]]<<endl;
        int A=(C-1);
        int B=(C-1);
        if(mec_dzax[i]==-1 && mec_aj[i]==-1)
        {
            ANS.pb({height[pos[i]]+1,-i});
            continue;
        }
        if(mec_dzax[i]!=-1)
        {
            A=pos[mec_dzax[i]];
        }
        if(mec_aj[i]!=-1)
        {
            B=pos[mec_aj[i]+1];
        }
        A=lca(pos[i],A);
        B=lca(pos[i],B);
        int H=height[pos[i]];
        /*if(i==6)
        {
            cout<<lca(3,5)<<endl;
            //cout<<pos[i]<<"dddd"<<endl;
            cout<<A1<<" rrr "<<B<<endl;
            cout<<mec_dzax[i]<<" ddd "<<mec_aj[i]<<endl;
            //cout<<H<<"ccc"<<endl;
        }*/
        ANS.pb({H-max(height[A],height[B]),-i});
    }
    //cout<<endl;
    sort(ANS.begin(),ANS.end());
    return (-ANS[ANS.size()-1].second);
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
/*
10 7 3
9 8 7 6 4 5 2 1 0
0 1
1 2
0 1
1 2
0 1
1 4
0 1
*/

Compilation message (stderr)

tournament.cpp: In function 'int push(int, int, int)':
tournament.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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