Submission #62456

#	Time	Username	Problem	Language	Result	Execution time	Memory
62456		theknife2001	Jousting tournament (IOI12_tournament)	C++17	0 / 100	23 ms	2076 KiB

tournament

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
const int N=5e3+55;
pair < int , int > b[N];
int tree[N*4];
int lazy[N*4];
bool vis[N];
int a[N];


void build(int l , int r , int node)
{
    if(r==l)
    {
        tree[node]=l;
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,node*2);
    build(mid+1,r,node*2+1);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}

void propagate(int l , int r , int node )
{
    tree[node]-=lazy[node];
    if(l!=r)
    {
        lazy[node*2]=lazy[node];
        lazy[node*2+1]=lazy[node];
    }
    lazy[node]=0;
}

int query(int l , int r , int node , int x)
{
    if(lazy[node])
        propagate(l,r,node);
    if(tree[node]==x&&l==r)
        return l;
    int mid=(l+r)/2;
    if(tree[node*2]>=x)
        return query(l,mid,node*2,x);
    else
        return query(mid+1,r,node*2+1,x);
}

void update(int l , int r , int node , int x , int y , int val)
{
    if(lazy[node])
        propagate(l,r,node);
    if(x<r||l>y)
        return ;
    if(x<=l&&y>=r)
    {
        lazy[node]+=val;
        propagate(l,r,node);
        return ;
    }
    int mid=(l+r)/2;
    update(l,mid,node*2,x,y,val);
    update(mid+1,r,node*2+1,x,y,val);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}


int GetBestPosition(int n, int m, int R, int *K, int *S, int *E) {
    int s,e;
    int best=0;
    int cur=0;
    build(0,n-1,1);
    for(int i=0;i<n;i++)
    {
        cur=0;
        for(int j=0;j<n;j++)
        {
            if(j==i)
            {
                a[j]=R;
                continue ;
            }
            a[j]=K[cur];
            cur++;
        }
        cur=0;
        int x,temp;
        for(int j=0;j<m;j++)
        {
            s=query(0,n-1,1,S[j]);
            e=query(0,n-1,1,E[j]);
            for(int k=s;k<=e;k++)
            {
                if(a[k]>temp)
                {
                    temp=a[k];
                    x=k;
                }
            }
            update(0,n-1,1,e+1,n-1,e-s);
            update(0,n-1,1,s,x-1,-1e5);
            update(0,n-1,1,x+1,e,-1e5);
            if(temp==R)
                cur++;
        }
        best=max(best,cur);
    }
    return best;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:96:17: warning: 'temp' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 if(a[k]>temp)
                 ^~
tournament.cpp:104:19: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
             update(0,n-1,1,x+1,e,-1e5);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~

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