oj.uz

Submission #62461

# Submission time Handle Problem Language Result Execution time Memory
62461 2018-07-28T16:37:21 Z theknife2001 Jousting tournament (IOI12_tournament) C++17
17 / 100
 1000 ms 2724 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 452 KB Output is correct
3 Correct 207 ms 536 KB Output is correct
4 Correct 241 ms 604 KB Output is correct
5 Correct 17 ms 604 KB Output is correct
6 Correct 261 ms 664 KB Output is correct
7 Correct 223 ms 664 KB Output is correct
8 Correct 243 ms 696 KB Output is correct
9 Correct 11 ms 696 KB Output is correct
10 Correct 42 ms 696 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 828 KB Output is correct
2 Execution timed out 1059 ms 1124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 2724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -