| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 321392 | neki | 마상시합 토너먼트 (IOI12_tournament) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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, vc<ll> K, vc<ll> S, vc<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;
}