| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 315893 | 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 N=1e5+5;
int n, c, last, k[N], s[N], e[N];
vector<pair<int,int>> ranges;
vector<int> pref;
vector<vector<int>> edges;
struct seg_tree{
int n;
vector<int> tree;
void mtree(int l,int r,int x){
if(l==r) {
tree[x]=1;
return;
}
int m=(l+r)/2;
mtree(l,m,x*2);
mtree(m+1,r,x*2+1);
tree[x]=tree[x*2] + tree[x*2+1];
}
void build(int N){
n=N;
tree.assign(n*4, 0);
mtree(1,n,1);
}
int get1(int val,int lx,int rx,int x){
if(lx==rx) return lx;
int m=(lx+rx)/2;
if(val <= tree[x*2]) return get1(val,lx,m,x*2);
else return get1(val,m+1,rx,x*2+1);
}
int get(int val){
return get1(val,1,n,1);
}
void update1(int l,int r,int lx,int rx,int x){
if(lx>r||rx<l) return;
if(lx>=l&&rx<=r){
tree[x]=0;
return;
}
int mid=(lx+rx)/2;
update1(l,r,lx,mid,x*2);
update1(l,r,mid+1,rx,x*2+1);
tree[x] = tree[x*2]+tree[x*2+1];
}
void update(int l,int r){
update1(l,r,1,n,1);
}
void print(){
for(int i=0;i<n*2;i++) cout<<tree[i]<<" ";
cout<<"\n";
}
int fr(){
return tree[1];
}
};
pair<int,int> dfs(int u){
pair<int,int> ans = make_pair(0,ranges[u].first);
for(auto v:edges[u]){
auto it=dfs(v);
ans = (it.first>ans.first ? it:ans);
}
if(pref[ranges[u].second-1] - pref[ranges[u].first-1] == 0)
ans.first++;
return ans;
}
bool cmp(pair<int,int> a,pair<int,int> b){
if(a.first==b.first) return a.second > b.second;
return a.first < b.first;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
//cout<<"WORKS\n";
n=N, c=C, last=R;
for(int i=0;i<n-1;i++) k[i+1]=K[i];
for(int i=0;i<c;i++) s[i]=S[i]+1, e[i]=E[i]+1;
seg_tree tree;
tree.build(n);
//tree.print();
for(int i=0;i<c;i++){
int l = tree.get(s[i]);
int r = ((e[i]+1 > tree.fr()) ? n : tree.get(e[i]+1)-1 );
//cout<<l<<" "<<r<<"\n";
ranges.push_back({l,r});
tree.update(l+1,r);
//tree.print();
}
sort(ranges.begin(), ranges.end(), cmp);
pref.assign(n+1,0);
edges.resize(n+1);
for(int i=1;i<n;i++) {
pref[i] += pref[i-1];
if(k[i] > last) pref[i]++;
}
for(int i=1; i<ranges.size(); i++){
int j=i-1, fr=ranges[i].first, sc=ranges[i].second;
while(!(fr>=ranges[j].first && sc<=ranges[j].second)&&j>=0) j--;
edges[j].push_back(i);
}
auto ans=dfs(0);
int ans1=ans.second-1;
return ans1;
}
/*
5 3
3
1 0 2 4
1 3
0 1
0 1
*/