| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 315692 | amunduzbaev | Jousting tournament (IOI12_tournament) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int NAX = 305;
int n, c, last, k[NAX], s[NAX], e[NAX], tmp2[NAX], pos[NAX];
void rangeupd(int i){
int l=s[i], r=e[i], j=0;
while(pos[j]!=l&&j<n) j++;
s[i]=j;
while(pos[j]<=r&&j<n){
pos[j]=l;
j++;
}
e[i]=j-1;
int upd=r-l;
for( ;j<n;j++){
pos[j]-=upd;
}
}
int solve(){
int st, m, j=0;
struct segtree{
vector<int> tree, treem;
int s;
int build(int n){
s=1;
while(s<n)s*=2;
tree.assign(s*2, 0);
for(int i=s;i<s+n;i++){
treem[i]=tmp2[i-s];
tree[i]=tmp2[i-s];
}
for(int i=s-1;i>0;i--){
treem[i]=max(treem[i*2],treem[i*2+1]);
}
return s;
}
void push(int l,int r,int x){
treem[x*2] = max(tree[x], treem[x*2]);
treem[x*2+1] = max(tree[x], treem[x*2+1]);
tree[x*2] = tree[x];
tree[x*2+1] = tree[x];
tree[x]=0;
}
int f_max(int l,int r,int lx,int rx,int x){
if(lx>=r||rx<=l) return 0;
if(lx==rx) return treem[x];
if(lx>=l&&rx<=r) return treem[x];
push(lx,rx,x);
int m=(lx+rx)/2;
return max(f_max(l,r,lx,m,x*2),
f_max(l,r,m+1,rx,x*2+1));
}
void add_range(int l,int r,int lx,int rx,int x,int val){
if(lx>=r||rx<=l) return;
if(lx>=l&&rx<=r){
tree[x]=val;
if(lx==rx) treem[x]=val;
return;
}
int m=(lx+rx)/2;
add_range(l,r,lx,m,x*2,val);
add_range(l,r,m+1,rx,x*2+1,val);
}
};
segtree t;
st=t.build(n);
for(int i=0; i<c; i++){
m=t.f_max(s[i],e[i],0,st,1);
t.add_range(s[i],e[i],0,st,1,m);
if(m==last) j++;
}
return j;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n=N, c=C, last=R;
for(int i=0;i<n-1;i++) k[i]=K[i], pos[i]=i;
pos[n-1]=n-1;
for(int i=0;i<c;i++) s[i]=S[i],e[i]=E[i];
for(int i=0;i<c;i++) rangeupd(i);
tmp2[0]=last;
for(int i=1;i<n;i++) tmp2[i]=k[i-1];
int ans=solve(0),mx=0;
for(int i=1;i<n;i++){
swap(tmp2[i],tmp2[i+1]);
int sol=solve();
if(sol>mx){
mx=sol;
ans=i;
}
}
return ans;
}
/*
5 3
3
1 0 2 4
1 3
0 1
0 1
*/