Submission #430449

#	Time	Username	Problem	Language	Result	Execution time	Memory
430449		TLP39	Jousting tournament (IOI12_tournament)	C++14	100 / 100	471 ms	4084 KiB

tournament

#include<bits/stdc++.h>
using namespace std;

int n,r;
int qs[100010]={};
int seg[400040];
bool lzy[400040]={};
bool marked[400040],bottom[400040];
void build(int v,int st,int ed)
{
    seg[v]=0;
    marked[v]=false;
    bottom[v]=false;
    if(st==ed)
    {
        bottom[v]=true;
        return;
    }
    int mid=(st+ed)>>1;
    build(v<<1,st,mid);
    build(1+(v<<1),mid+1,ed);
}

void push_down(int v,int l,int r)
{
    if(!marked[v] || bottom[v]) return;
    marked[v]=false;
    marked[v<<1]=marked[1+(v<<1)]=true;
    lzy[v<<1]=true;
    lzy[1+(v<<1)]=true;
    int mid=(l+r)>>1;
    seg[v<<1]=max(seg[v<<1],mid-l+1);
    seg[1+(v<<1)]=max(seg[1+(v<<1)],r-mid);
    seg[v]=seg[v<<1]+seg[1+(v<<1)];
    lzy[v]=false;
}

void upd(int v,int l,int r,int st,int ed)
{
    if(st>ed) return;
    if(l==st && r==ed)
    {
        lzy[v]=true;
        marked[v]=true;
        seg[v]=max(seg[v],r-l+1);
        return;
    }
    push_down(v,l,r);
    int mid=(l+r)>>1;
    upd(v<<1,l,mid,st,min(mid,ed));
    upd(1+(v<<1),mid+1,r,max(mid+1,st),ed);
    seg[v]=seg[v<<1]+seg[1+(v<<1)];
}

int que(int v,int l,int r,int st,int ed)
{
    if(st>ed) return 0;
    if(l==st && r==ed) return seg[v];
    push_down(v,l,r);
    int mid=(l+r)>>1;
    return que(v<<1,l,mid,st,min(mid,ed))+
    que(1+(v<<1),mid+1,r,max(mid+1,st),ed);
}

int getpos_low(int k)
{
    int hi=n,low=1,av;
    while(hi>low)
    {
        av=(hi+low)>>1;
        if(av-que(1,1,n,1,av)>=k) hi=av;
        else low=av+1;
    }
    return hi;
}

int getpos_hi(int k)
{
    int hi=n,low=1,av;
    while(hi>low)
    {
        av=(hi+low+1)>>1;
        if(av-que(1,1,n,1,av)<=k) low=av;
        else hi=av-1;
    }
    return hi;
}

int qs2[100010]={};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    r=R;
    for(int i=1;i<n;i++)
    {
        qs[i]=qs[i-1]+(K[i-1]<R);
    }
    build(1,1,n);
    int hi,low;
    for(int i=0;i<C;i++)
    {
        hi=getpos_hi(E[i]+1);
        low=getpos_low(S[i]+1);
        if(qs[hi-1]-qs[low-1]==hi-low)
        {qs2[low]++;
        qs2[hi+1]--;}
        upd(1,1,n,low+1,hi);
    }
    for(int i=1;i<=n;i++) qs2[i]+=qs2[i-1];
    int best_pos,res=-1;
    for(int i=1;i<=n;i++)
    {
        if(qs2[i]>res)
        {
            res=qs2[i];
            best_pos=i-1;
        }
    }
    return best_pos;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:118:12: warning: 'best_pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |     return best_pos;
      |            ^~~~~~~~

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