Submission #321393

#	Time	Username	Problem	Language	Result	Execution time	Memory
321393		neki	Jousting tournament (IOI12_tournament)	C++14	0 / 100	15 ms	2028 KiB

tournament

#include <bits/stdc++.h>
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll int
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
#define intmax INT_MAX/2
using namespace std;
#define mn 1010
#define pa pair<ll, ll>
#define ld long double 
pa dp[2 * mn];
ll ran[2 * mn], n;
ll getmr(ll l, ll r){
    ll ret=-1;
    for(l+=n,r+=n;l<r;l>>=1, r>>=1){
        if(l&1) ret=max(ran[l++], ret);
        if(r&1) ret=max(ran[--r], ret);
    }
    return ret;
}
void updran(ll pos, ll val){
    for(pos+=n;pos>0;pos>>=1) ran[pos]=max(ran[pos], val);
}

pa max(pa a, pa b){
    if(a.fi>b.fi) return a;
    else if(b.fi>a.fi) return b;
    return (a.se<b.se) ? a:b;
}
pa getdp(ll l, ll r){
    pa ret={-1, intmax};
    for(l+=n,r+=n;l<r;l>>=1, r>>=1){
        if(l&1) ret=max(dp[l++], ret);
        if(r&1) ret=max(dp[--r], ret);
    }
    return ret;
}
void upddp(ll pos, pa val){
    for(pos+=n;pos>0;pos>>=1) dp[pos]=max(dp[pos], val);
}


ll ind[2 * mn];
void updind(ll l, ll r, ll val){
    for(l+=n,r+=n;l<r;l>>=1, r>>=1){
        if(l&1) ind[l++]+=val;
        if(r&1) ind[--r]+=val;
    }
}
ll getind(ll pos){
    ll ret=0;
    for(pos+=n;pos>0;pos>>=1) ret+=ind[pos];
    return min(ret, n);
}
ll GetBestPosition(ll N, ll C, ll R, ll K[], ll S[], ll E[]){
    n=N;
    loop(i, 0, n) updind(i, i+1, i);
    loop(i, 0, n-1) updran(i, K[i]);
    loop(i, 0, 2 * mn) dp[i]=make_pair(-1, intmax);
    
    loop(i, 0, C){
        ll s=getind(S[i]),  e=getind(E[i]+1);
        pa ans={0, s};ans=max(ans, getdp(s, e));
        if(R>getmr(s, e-1)) ans.fi++;
        upddp(s, ans);
        updind(s+1, n, e-s-1);
    }
    pa ans={-1, 0};ans=max(ans, getdp(0, n));
    return ans.se;
}

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