| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 913182 | Sir_Ahmed_Imran | Ideal city (IOI12_city) | C++17 | 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.
///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define MAXN 100000
int k[MAXN];
int sum[4*MAXN];
int MAX[4*MAXN];
ll lazy[4*MAXN];
pair<ll,int> POS[4*MAXN];
void add_sum(int p,int x,int v=1,int s=0,int e=MAXN){
sum[v]+=x;
if(e-s==1) return;
int mid,lc,rc;
mid=(s+e)/2;
lc=2*v;
rc=2*v+1;
if(p<mid) add_sum(p,x,lc,s,mid);
else add_sum(p,x,rc,mid,e);
}
int get_sum(int l,int r,int v=1,int s=0,int e=MAXN){
if(l>=e || s>=r || l>=r) return 0;
if(l<=s && e<=r) return sum[v];
int mid,lc,rc;
mid=(s+e)/2;
lc=2*v;
rc=2*v+1;
return get_sum(l,r,lc,s,mid)+get_sum(l,r,rc,mid,e);
}
void build_max(int v=1,int s=0,int e=MAXN){
if(e-s==1){
MAX[v]=k[s];
return;
}
int mid,lc,rc;
mid=(s+e)/2;
lc=2*v;
rc=2*v+1;
build_max(lc,s,mid);
build_max(rc,mid,e);
MAX[v]=max(MAX[lc],MAX[rc]);
}
int get_max(int l,int r,int v=1,int s=0,int e=MAXN){
if(l>=e || s>=r) return 0;
if(l<=s && e<=r) return MAX[v];
int mid,lc,rc;
mid=(s+e)/2;
lc=2*v;
rc=2*v+1;
return max(get_max(lc,s,mid),get_max(rc,mid,e));
}
void build_pos(int v=1,int s=0,int e=MAXN){
POS[v]={0,s};
if(e-s==1) return;
int mid,lc,rc;
mid=(s+e)/2;
lc=2*v;
rc=2*v+1;
build_pos(lc,s,mid);
build_pos(rc,mid,e);
POS[v]=max(POS[lc],POS[rc]);
}
void push(int v){
int lc,rc;
lc=2*v;
rc=2*v+1;
POS[lc].ff+=lazy[v];
POS[rc].ff+=lazy[v];
lazy[lc]+=lazy[v];
lazy[rc]+=lazy[v];
lazy[v]=0;
}
void add_pos(int l,int r,ll x,int v=1,int s=0,int e=MAXN){
if(l>=e || s>=r) return;
if(l<=s && e<=r){
POS[v].ff+=x;
lazy[v]+=x;
return;
}
int mid,lc,rc;
mid=(s+e)/2;
lc=2*v;
rc=2*v+1;
add_pos(l,r,x,lc,s,mid);
add_pos(l,r,x,rc,mid,e);
POS[v]=max(POS[lc],POS[rc]);
}
pair<ll,int> get_pos(int l,int r,int v=1,int s=0,int e=MAXN){
if(l>=e || s>=r) return {0,0};
if(l<=s && e<=r) return POS[v];
int mid,lc,rc;
mid=(s+e)/2;
lc=2*v;
rc=2*v+1;
push(v);
return max(get_pos(l,r,lc,s,mid),get_pos(l,r,rc,mid,e));
}
int GetBestPosition(int n,int m,int r,int K[MAXN],int s[MAXN],int e[MAXN]){
int p,q;
for(int i=0;i<n-1;i++)
k[i]=K[i];
build_max();
build_pos();
pair<ll,int> pi{0,0};
for(int i=0;i<m;i++){
p=s[i];
q=e[i];
p+=get_sum(0,p);
q+=get_sum(0,q);
if(get_max(p,q)>r)
add_pos(p,q+1,-1e5);
else{
add_pos(p,q+1,1);
pi=max(pi,get_pos(p,q+1));
}
}
return pi.ss;
}