Submission #62459

#	Time	Username	Problem	Language	Result	Execution time	Memory
62459		theknife2001	Jousting tournament (IOI12_tournament)	C++17	0 / 100	19 ms	1960 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)
{
    lazy[node]=0;
    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);
//    cout<<l<<' '<<r<<' '<<tree[node]<<' '<<x<<endl;
    if(tree[node]==x&&l==r)
        return l;
    if(l>r)
        assert(0);
    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(l>y||r<x||x>y)
        return ;
//    cout<<l<<' '<<r<<' '<<x<<' '<<y<<' '<<val<<endl;
    if(l>=x&&r<=y)
    {
        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]);
}

void update1(int l , int r , int node , int ind , int val)
{
    if(lazy[node])
        propagate(l,r,node);
    if(l==r&&l==ind)
    {
        tree[node]=val;
        return ;
    }
    int mid=(l+r)/2;
    if(ind<=mid)
        update1(l,mid,node*2,ind,val);
    else
        update1(mid+1,r,1+node*2,ind,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 ret,best=0;
    int cur=0;
    for(int i=0;i<n;i++)
    {
        cur=0;
        for(int j=0;j<n;j++)
        {
            if(j==i)
            {
                a[j]=R;
//                cout<<a[j]<<' ';
                continue ;
            }
            a[j]=K[cur];
//            cout<<a[j]<<' ';
            cur++;
        }
//        cout<<endl;
        build(0,n-1,1);
        cur=0;
        int x,temp=0;
        for(int j=0;j<m;j++)
        {
//            cout<<S[j]<<' '<<E[j]<<endl;
            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,S[j]-E[j]);
            update(0,n-1,1,s,x-1,-1e5);
            update(0,n-1,1,x+1,e,-1e5);
            update1(0,n-1,1,x,S[j]);
            if(temp==R)
                cur++;
        }
        if(cur>best)
        {
            ret=i;
            best=cur;
        }
    }
    return ret;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:141:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ret;
            ^~~
tournament.cpp:130: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