| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 372491 | denkendoemeer | Meetings (IOI18_meetings) | 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 "meetings.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct lc
{
int a,l,r;
ll b,lazy;
lc():a(0),l(0),r(0),b(0x3fffffffffffffffLL),lazy(0){}
};
pair<int,int>aint[1<<21];
lc lt[1<<21],rt[1<<21];
vector<long long>ans;
vector<tuple<int,int,int>>q[750001];
pair<int,int> calc(int st,int dr)
{
pair<int,int>rez(-1,-1);
for(st+=1<<20,dr+=1<<20;st<=dr;st>>=1,dr>>=1){
if (st&1)
rez=max(rez,aint[st++]);
if (~dr&1)
rez=max(rez,aint[dr--]);
}
return rez;
}
void push(lc *aint,int nod,int st,int dr)
{
if (aint[nod].lazy){
aint[nod].b+=aint[nod].lazy;
if (st<dr){
aint[2*nod].lazy+=aint[nod].lazy;
aint[2*nod+1].lazy+=aint[nod].lazy;
}
aint[nod].lazy=0;
}
}
int semn(ll x)
{
if (x<0)
return -1;
return x>0;
}
void addlin(lc *aint,int l,int r,int a,long long b,int nod=1,int st=0,int dr=(1<<20)-1)
{
int mij=(st+dr)/2;
push(aint,nod,st,dr);
if (r<l || r<st || dr<l)
return;
if (l<=st && dr<=r){
ll st2=1LL*a*st+b,mij2=1LL*a*mij+b,dr2=1LL*a*dr+b,st3=1LL*aint[nod].a*st+aint[nod].b,mij3=1LL*aint[nod].a*mij+aint[nod].b,dr3=1LL*aint[nod].a*dr+aint[nod].b;
if (mij2<mij3){
swap(aint[nod].a,a);
swap(aint[nod].b,b);
swap(st3,st2);
swap(mij3,mij2);
swap(dr3,dr2);
}
if (st3<=st2 && dr3<=dr2)
return;
if (semn(st2-st3)*semn(mij2-mij3)<0 || mij2==mij3 && st2<st3)
addlin(aint,l,r,a,b,2*nod,st,mij);
else
addlin(aint,l,r,a,b,2*nod+1,mij+1,dr);
return;
}
addlin(aint,l,r,a,b,2*nod,st,mij);
addlin(aint,l,r,a,b,2*nod+1,mij+1,dr);
}
void add(lc *aint,int l,int r,ll val,int nod=1,int st=0,int dr=(1<<20)-1)
{
int mij=(st+dr)/2;
push(aint,nod,st,dr);
if (r<l || r<st || dr<l)
return;
if (l<=st && dr<=r){
aint[nod].lazy=val;
push(aint,nod,st,dr);
return;
}
add(aint,l,r,val,2*nod,st,mij);
add(aint,l,r,val,2*nod+1,mij+1,dr);
}
long long calcy(lc *aint,int poz,int nod=1,int st=0,int dr=(1<<20)-1)
{
int mij=(st+dr)/2;
push(aint,nod,st,dr);
if (st==dr)
return 1LL*aint[nod].a*poz+aint[nod].b;
return min(poz<=mij?calcy(aint,poz,2*nod,st,mij):calcy(aint,poz,2*nod+1,mij+1,dr),1LL*aint[nod].a*poz+aint[nod].b);
}
void solve(int st,int dr)
{
if (st>dr)
return;
auto [a,b]=get_max(s,e);
solve(st,b-1);
solve(b+1,dr);
for(auto [l,r,i]:q[b])
ans[i]=min(calcy(lt,l)+(r-b+1LL)*a,calcy(rt,r)+(b-l+1LL)*a);
add(lt,st,b-1,(dr-b+1LL)*a);
addlin(lt,st,b,-a,(b<dr?calcy(lt,b+1):0)+a*(b+1LL));
add(rt,b+1,dr,(b-st+1LL)*a);
addlin(rt,b,dr,a,(st<b?calcy(rt,b-1):0)+a*(1LL-b));
}
vector<long long> minimum_costs(vector<int>H,vector<int>L,vector<int>R)
{
int n=H.size(),m=L.size();
ans.resize(m);
int i;
for(i=0;i<n;i++)
aint[(1<<20)+i+1]={H[i],i+1};
for(i=(1<<20);--i;)
aint[i]=max(aint[2*i],aint[2*i+1]);
for(i=0;i<m;i++){
if (++L[i]<++R[i])
q[calc(L[i],R[i]).second].emplace_back(L[i],R[i],i);
else
ans[i]=H[L[i]-1];
}
solve(1,n);
return ans;
}