제출 #62461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62461		theknife2001	마상시합 토너먼트 (IOI12_tournament)	C++17	17 / 100	1059 ms	2724 KiB

tournament

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

using namespace std;
const int N=5e3+55;
int tree[N*4];
pair < int , int > tree1[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);
    if(tree[node]==x&&l==r)
        return l;
//    if(l>r)
//        assert(0);
    int mid=(l+r)/2;
    if(lazy[node*2])
        propagate(l,mid,node*2);
//    cout<<l<<' '<<r<<' '<<tree[node]<<' '<<tree[node*2]<<' '<<x<<endl;
    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);
    if(lazy[node*2])
        propagate(l,mid,node*2);
    if(lazy[node*2+1])
        propagate(mid+1,r,node*2+1);
    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);
    if(lazy[node*2])
        propagate(l,mid,node*2);
    if(lazy[node*2+1])
        propagate(mid+1,r,node*2+1);
    tree[node]=max(tree[node*2],tree[node*2+1]);

}

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

pair < int , int > query1(int l , int r , int node , int x , int y)
{
    if(l>y||r<x)
        return {0,0};
    if(l>=x&&r<=y)
        return tree1[node];
    int mid=(l+r)/2;
    return max(
    query1(l,mid,node*2,x,y),
    query1(mid+1,r,node*2+1,x,y)
    );
}

int GetBestPosition(int n, int m, int R, int *K, int *S, int *E) {
    int s,e;
    int ret,best=-1;
    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);
        build1(0,n-1,1);
        cur=0;
        pair < int , int > temp={0,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]);
//            cout<<s<<' '<<e<<endl;
            temp=query1(0,n-1,1,s,e);
            update(0,n-1,1,e+1,n-1,S[j]-E[j]);
            update(0,n-1,1,s,e,-1e5);
//            cout<<x<<endl;
            update1(0,n-1,1,temp.se,S[j]);
            if(temp.fi==R)
                cur++;
        }
        if(cur>best)
        {
            ret=i;
            best=cur;
        }
    }
    return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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