| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 537951 | perchuts | 마상시합 토너먼트 (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
int bit[maxn], idx[maxn], N, mxpower, best, indbest, rk;
bool can[maxn];
struct node{
int mx, ind, mxind, mnind, resp;
vector<int>adj;
};
void update(int x){
while(x<=N)bit[x]--, x += x&(-x);
}
int query(int x){
int ans = 0;
int mask = 0,tmp = mxpower, sum = 0;
while(tmp>=0){
if((mask|(1<<tmp))<=N&&sum + bit[mask|(1<<tmp)]<x)mask|=(1<<tmp), sum += bit[mask];
--tmp;
}
return mask+1;
}
node nodes[2*maxn];
ii dfs(int u){
can[u] = 1;
if(u<=N)return {nodes[u].mx>rk,1};
int lvl = 0, qnt = 0, resp = -1;
for(auto v:nodes[u].adj){
ii cur = dfs(v);
can[u]&=can[v];
if(cur.first==1&&v>=N)resp = nodes[v].resp;
ckmax(nodes[u].mxind,nodes[v].mxind), ckmin(nodes[u].mnind,nodes[v].mnind);
qnt += cur.first;ckmax(lvl,cur.second);
if(ckmax(nodes[u].mx,nodes[v].mx))nodes[u].ind = nodes[v].ind;
}
// cout<<u<<" "<<can[u]<<" "<<lvl<<" "<<qnt<<" "<<resp<<endl;
// cout<<nodes[u].mnind<<" "<<nodes[u].mxind<<" "<<nodes[u].mx<<" "<<nodes[u].ind<<endl;
if(can[u]){
if(qnt>1||(qnt==1&&nodes[u].ind!=nodes[u].mxind))can[u] = 0;
if(can[u]){
if(resp!=-1)nodes[u].resp = resp;
else nodes[u].resp = nodes[u].mnind;
if(ckmax(best,lvl))indbest = nodes[u].resp;
if(best==lvl)ckmin(indbest,nodes[u].resp);
}
}
return {qnt,lvl+1};
}
int GetBestPosition(int n, int c, int R, int *k, int *s, int *e){
//construir uma arvore representando todas as justas
//depois de construir a arvore, o problema vira uma simples tree dp
N = n, rk = R;
while((1<<mxpower)<=n)++mxpower;
mxpower--;
for(int i=1;i<=n;++i)bit[i] = i&(-i), idx[i] = i, nodes[i].mx = (i!=n?k[i-1]:R), nodes[i].ind = nodes[i].mxind = nodes[i].mnind = i-1;
for(int i=1;i<=c;++i){
vector<int>v;
int l = s[i-1]+1, r = e[i-1]+1;
for(int j=l;j<=r;++j)v.pb(query(j));
for(auto x:v){
nodes[n+i].adj.pb(idx[x]);
if(x!=v[0])update(x);
}
idx[v[0]] = n+i;
nodes[n+i].mnind = inf;
}
dfs(n+c);
// for(int i=1;i<=n+c;++i){
// cout<<"neighbors of "<<i<<endl;
// for(auto x:nodes[i].adj)cout<<x<<" ";
// cout<<endl;
// cout<<"min index is "<<nodes[i].mnind<<endl;
// cout<<"max is "<<nodes[i].mx<<" "<<nodes[i].ind<<endl;
// cout<<endl;
// }
return indbest;
}
int k[maxn],s[maxn],e[maxn];
int main(){_
int n,c,r;cin>>n>>c>>r;
for(int i=0;i<n-1;++i)cin>>k[i];
for(int i=0;i<c;++i)cin>>s[i];
for(int i=0;i<c;++i)cin>>e[i];
cout<<GetBestPosition(n,c,r,k,s,e)<<endl;
}