oj.uz

Submission #430449

# Submission time Handle Problem Language Result Execution time Memory
430449 2021-06-16T13:56:32 Z TLP39 Jousting tournament (IOI12_tournament) C++14
100 / 100
 471 ms 4084 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 14 ms 516 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 19 ms 460 KB Output is correct
5 Correct 17 ms 508 KB Output is correct
6 Correct 10 ms 460 KB Output is correct
7 Correct 14 ms 460 KB Output is correct
8 Correct 14 ms 516 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 16 ms 524 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 2124 KB Output is correct
2 Correct 471 ms 4036 KB Output is correct
3 Correct 57 ms 3140 KB Output is correct
4 Correct 460 ms 4024 KB Output is correct
5 Correct 420 ms 3908 KB Output is correct
6 Correct 307 ms 3652 KB Output is correct
7 Correct 451 ms 4084 KB Output is correct
8 Correct 454 ms 4012 KB Output is correct
9 Correct 20 ms 3140 KB Output is correct
10 Correct 38 ms 3308 KB Output is correct