| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1111874 | epicci23 | Meetings (IOI18_meetings) | 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.
#include "bits/stdc++.h"
#include "meetings.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll INF = 1e18;
const int N = 1e6 + 5;
ll ar[N];
array<ll,4> seg[4*N];
array<ll,4> merge(array<ll,4> a,array<ll,4> b){
if(a[0]==-1) return b;
if(b[0]==-1) return a;
array<ll,4> res;
res[3]=a[3]+b[3];
res[0]=max(a[0],b[0]);
res[0]=max(res[0],a[2]+b[1]);
res[2]=b[2];
if(b[0]==b[3]) res[2]=max(res[2],b[0]+a[2]);
res[1]=a[1];
if(a[0]==a[3]) res[1]=max(res[1],a[0]+b[1]);
res[0]=max(res[0],res[1]);
res[0]=max(res[0],res[2]);
return res;
}
void build(int rt,int l,int r){
if(l==r){
seg[rt]={0,0,0,1};
if(ar[l]==1) seg[rt]={1,1,1,1};
return;
}
int m = (l+r)/2;
build(rt*2,l,m),build(rt*2+1,m+1,r);
seg[rt]=merge(seg[rt*2],seg[rt*2+1]);
}
array<int,4> query(int rt,int l,int r,int gl,int gr){
if(r<gl || l>gr) return {-1,-1,-1,-1};
if(l>=gl && r<=gr) return seg[rt];
int m=(l+r)/2;
return merge(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R){
ll n,q;
n=sz(H),q=sz(L);
vector<ll> res;
for(int i=1;i<=n;i++) ar[i]=H[i-1];
if(n<=5005){
ll mx[n+5][n+5];
for(int i=1;i<=n;i++){
ll hm = ar[i];
for(int j=i;j<=n;j++){
hm=max(hm,ar[j]);
mx[i][j]=hm;
}
}
ll pre[n+5][n+5];
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++){
ll cur = 0;
for(int j=i;j<=n;j++){
cur += mx[i][j];
pre[i][j] = cur;
}
cur = 0;
for(int j=i;j>=1;j--){
cur += mx[j][i];
pre[i][j] = cur;
}
}
for(int i=0;i<q;i++){
ll l,r;
l=L[i]+1,r=R[i]+1;
ll xd = INF;
for(int i=l;i<=r;i++){
ll curi = pre[i][l] + pre[i][r] - ar[i];
xd = min(xd, curi);
}
res.push_back(xd);
}
}
else{
build(1,1,n);
for(int i=0;i<q;i++){
ll l = L[i]+1 , r = R[i] + 1;
auto u = query(1,1,n,l,r);
res.push_back(2LL*(r-l+1LL) - u[0]);
}
}
return res;
}
/*void _(){
int n,q;
cin >> n >> q;
int ar[n+5];
for(int i=1;i<=n;i++) cin >> ar[i];
int mx[n+5][n+5];
for(int i=1;i<=n;i++){
int hm = ar[i];
for(int j=i;j<=n;j++){
hm=max(hm,ar[j]);
mx[i][j]=hm;
}
}
int pre[n+5][n+5];
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++){
int cur = 0;
for(int j=i;j<=n;j++){
cur += mx[i][j];
pre[i][j] = cur;
}
cur = 0;
for(int j=i;j>=1;j--){
cur += mx[j][i];
pre[i][j] = cur;
}
}
while(q--){
int l,r;
cin >> l >> r;
int res = INF;
for(int i=l;i<=r;i++){
int curi = pre[i][l] + pre[i][r] - ar[i];
res = min(res, curi);
}
cout << res << '\n';
}
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/