oj.uz

Submission #708973

# Submission time Handle Problem Language Result Execution time Memory
708973 2023-03-13T03:13:10 Z ToroTN Jousting tournament (IOI12_tournament) C++14
100 / 100
 472 ms 7684 KB 
#include<bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
int n,c,r,a[100005],x[100005],y[100005],seg[400005],lz[400005],seg2[400005];
int l,late,sweep[100005];
void build2(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        seg2[tree]=a[st];
        return;
    }
    build2(2*tree,st,md);
    build2(2*tree+1,md+1,ed);
    seg2[tree]=max(seg2[2*tree],seg2[2*tree+1]);
}
int query2(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>r||ed<l)return -1e9;
    if(st>=l&&ed<=r)return seg2[tree];
    return max(query2(2*tree,st,md,l,r),query2(2*tree+1,md+1,ed,l,r));
}
void build(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        seg[tree]=1;
        return;
    }
    build(2*tree,st,md);
    build(2*tree+1,md+1,ed);
    seg[tree]=seg[2*tree]+seg[2*tree+1];
}
void update(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>=l&&ed<=r)lz[tree]=1;
    if(st!=ed)
    {
        if(lz[tree]==1)
        {
            lz[2*tree]=1;
            lz[2*tree+1]=1;
        }
    }
    if(lz[tree]==1)seg[tree]=0;
    lz[tree]=0;
    if(st>r||ed<l)return;
    if(st>=l&&ed<=r)return;
    update(2*tree,st,md,l,r);
    update(2*tree+1,md+1,ed,l,r);
    seg[tree]=seg[2*tree]+seg[2*tree+1];
}
int query(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st!=ed)
    {
        if(lz[tree]==1)
        {
            lz[2*tree]=1;
            lz[2*tree+1]=1;
        }
    }
    if(lz[tree]==1)seg[tree]=0;
    lz[tree]=0;
    if(st>r||ed<l)return 0;
    if(st>=l&&ed<=r)return seg[tree];
    return query(2*tree,st,md,l,r)+query(2*tree+1,md+1,ed,l,r);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) 
{
    n=N,c=C,late=R+1;
    if(n==1)return 0;
    for(int i=0;i<N-1;i++)
    {
        a[i+1]=K[i]+1;
    }
    for(int i=0;i<c;i++)
    {
        x[i+1]=S[i]+1,y[i+1]=E[i]+1;
    }
    build2(1,1,n-1);
    /*for(int i=1;i<n;i++)printf("%d ",a[i]);
    printf("\n");
    for(int i=1;i<=c;i++)printf("%d %d\n",x[i],y[i]);*/
    /*for(int i=1;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
            printf("%d %d %d\n",i,j,query2(1,1,n-1,i,j));
        }
    }*/
    build(1,1,n);
    for(int i=1;i<=c;i++)
    {
        int st=1,md,ed=n;
        //printf("x=%d y=%d\n",x[i],y[i]);
        while(ed>=st)
        {
            md=(st+ed)/2;
            if(query(1,1,n,1,md)<x[i])
            {
                st=md+1;
            }else
            {
                ed=md-1;
            }
        }
        l=st;
        //printf("%d %d %d\n",st,md,ed);
        st=1,ed=n;
        while(ed>=st)
        {
            md=(st+ed)/2;
            if(query(1,1,n,1,md)<=y[i])
            {
                st=md+1;
            }else
            {
                ed=md-1;
            }
        }
        //printf("%d %d %d\n",st,md,ed);
        r=ed;
        if(late>query2(1,1,n-1,l,r-1))
        {
            sweep[l]+=1;
            sweep[r+1]-=1;
        }
        if(l<r)
        {
            //printf("chk%d\n",i);
            update(1,1,n,l+1,r);
        }
        /*for(int j=1;j<=n;j++)
        {
            for(int k=j;k<=n;k++)
            {
                printf("%d %d %d\n",j,k,query(1,1,n,j,k));
            }
        }
        printf("%d %d\n\n",l,r);*/
        //break;
    }
    for(int i=1;i<=n;i++)sweep[i]=sweep[i-1]+sweep[i];
    int mx=-1e9,ans;
    for(int i=1;i<=n;i++)
    {
        if(sweep[i]>mx)mx=sweep[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(sweep[i]==mx)
        {
            ans=i-1;
            break;
        }
    }
    return ans;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:150:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  150 |     int mx=-1e9,ans;
      |                 ^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 13 ms 720 KB Output is correct
3 Correct 2 ms 580 KB Output is correct
4 Correct 13 ms 724 KB Output is correct
5 Correct 18 ms 596 KB Output is correct
6 Correct 10 ms 596 KB Output is correct
7 Correct 14 ms 724 KB Output is correct
8 Correct 14 ms 732 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 15 ms 724 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 2964 KB Output is correct
2 Correct 417 ms 7684 KB Output is correct
3 Correct 38 ms 4336 KB Output is correct
4 Correct 411 ms 7608 KB Output is correct
5 Correct 433 ms 7524 KB Output is correct
6 Correct 309 ms 6800 KB Output is correct
7 Correct 398 ms 7644 KB Output is correct
8 Correct 472 ms 7644 KB Output is correct
9 Correct 12 ms 4180 KB Output is correct
10 Correct 35 ms 5296 KB Output is correct