| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 707215 | lam | 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 <bits/stdc++.h>
#include "meetings.h"
#define int long long
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define ff first
#define ss second
const int maxn = 8e5 + 10;
const int inf = 1e18;
int n,q;
deque<int> dq;
vector <int> adj[maxn];
int in[maxn],out[maxn],cnt;
int par[21][maxn];
int h[maxn];
ii range[maxn];
vector <iii> queries[maxn];
int res[maxn];
struct line
{
int a,b;
};
int calc(line x, int idx)
{
return x.a*idx + x.b;
}
struct segtree
{
line f[4*maxn], lazy[4*maxn];
void pushsum(int x, int lx, int rx, line val)
{
f[x].a += val.a; f[x].b += val.b;
lazy[x].a += val.a; lazy[x].b += val.b;
}
void downsum(int x, int lx, int rx)
{
if (lx==rx) return;
int mid=(lx+rx)/2;
if (lazy[x].a!=0||lazy[x].b!=0)
{
pushsum(2*x,lx,mid,lazy[x]);
pushsum(2*x+1,mid+1,rx,lazy[x]);
lazy[x]={0,0};
}
}
void update(int x, int lx, int rx, line val)
{
if (lx==rx)
{
if (calc(f[x],lx)>calc(val,lx)) swap(f[x],val);
return;
}
int mid=(lx+rx)/2;
downsum(x,lx,rx);
if (calc(f[x],mid)>calc(val,mid)) swap(f[x],val);
if (calc(f[x],lx)>calc(val,lx)) update(2*x,lx,mid,val);
else update(2*x+1,mid+1,rx,val);
}
void downline(int x, int lx, int rx)
{
if (lx==rx) return;
int mid=(lx+rx)/2;
update(2*x,lx,mid,f[x]);
update(2*x+1,mid+1,rx,f[x]);
f[x]={0,inf};
}
void update_min(int x, int lx, int rx, int l, int r, line val)
{
if (lx>r||rx<l) return;
if (lx>=l&&rx<=r)
{
update(x,lx,rx,val);
return;
}
int mid=(lx+rx)/2;
downsum(x,lx,rx);
update_min(2*x,lx,mid,l,r,val);
update_min(2*x+1,mid+1,rx,l,r,val);
}
void add(int x, int lx, int rx, int l, int r, line val)
{
if (lx>r||rx<l) return;
if (lx>=l&&rx<=r)
{
pushsum(x,lx,rx,val);
return;
}
int mid=(lx+rx)/2;
downsum(x,lx,rx);
downline(x,lx,rx);
add(2*x,lx,mid,l,r,val);
add(2*x+1,mid+1,rx,l,r,val);
}
int qry(int x, int lx, int rx, int idx)
{
if (lx==rx) return calc(f[x],lx);
int mid=(lx+rx)/2;
downsum(x,lx,rx);
int temp = calc(f[x],idx);
if (idx<=mid) return min(temp,qry(2*x,lx,mid,idx));
else return min(temp,qry(2*x+1,mid+1,rx,idx));
}
void build(int x, int lx, int rx)
{
lazy[x]={0,0};
f[x]={0,0};
if (lx==rx) return;
int mid=(lx+rx)/2;
build(2*x,lx,mid); build(2*x+1,mid+1,rx);
}
};
segtree pre,suf;
void dfs(int x, int p)
{
par[0][x]=p;
for (int i=1; i<=20; i++) par[i][x]=par[i-1][par[i-1][x]];
in[x]=++cnt;
for (int i:adj[x])
if (i!=p) dfs(i,x);
out[x]=cnt;
}
bool check(int u, int v)
{
return in[u]<=in[v]&&out[v]<=out[u];
}
int lca(int u, int v)
{
if (check(u,v)) return u;
if (check(v,u)) return v;
for (int i=20; i>=0; i--)
if (!check(par[i][u],v)) u=par[i][u];
return par[0][u];
}
bool cmp(int x, int y)
{
if (h[x]!=h[y]) return h[x]<h[y];
return x>y;
}
vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L,
vector<int32_t> R) {
n=H.size(); q=L.size();
for (int i=1; i<=n; i++) h[i]=H[i-1];
for (int i=1; i<=n; i++)
{
while (!dq.empty()&&h[dq.back()]<h[i]) dq.pop_back();
if (!dq.empty()) adj[dq.back()].push_back(i), range[i].ff = dq.back()+1;
else range[i].ff=1;
dq.push_back(i);
}
while (!dq.empty()) dq.pop_back();
for (int i=n; i>=1; i--)
{
while (!dq.empty()&&h[dq.back()]<=h[i]) dq.pop_back();
if (!dq.empty()) adj[dq.back()].push_back(i), range[i].ss = dq.back()-1;
else range[i].ss=n;
dq.push_back(i);
}
int root = -1;
for (int i=1; i<=n; i++)
if (range[i].ff==1&&range[i].ss==n) root=i;
dfs(root,root);
for (int i=1; i<=q; i++)
{
int l,r; l=L[i-1]; r=R[i-1];
int x = lca(l,r);
queries[x].push_back({{l,r},i});
}
vector <int> id;
for (int i=1; i<=n; i++) id.push_back(i);
sort(id.begin(),id.end(),cmp);
pre.build(1,1,n);
suf.build(1,1,n);
for (int it:id)
{
int ll = range[it].ff; int rr=range[it].ss;
// cout<<it<<" == "<<ll<<' '<<rr<<'\n';
for (iii i:queries[it])
{
int ans = 1e18;
if (i.ff.ff<it) ans = min(ans,suf.qry(1,1,n,i.ff.ff) + (i.ff.ss-it+1)*h[it]);
if (i.ff.ss>it) ans = min(ans,pre.qry(1,1,n,i.ff.ss) + (it-i.ff.ff+1)*h[it]);
if (i.ff.ff==it&&i.ff.ss==it) ans = h[it];
res[i.ss]=ans;
}
int x = suf.qry(1,1,n,ll);
int y = pre.qry(1,1,n,rr);
suf.add(1,1,n,ll,it,{0,(rr-it+1)*h[it]});
pre.add(1,1,n,it,rr,{0,(it-ll+1)*h[it]});
suf.update_min(1,1,n,ll,it,{-h[it],(it+1)*h[it] + y});
pre.update_min(1,1,n,it,rr,{h[it],x - (it-1)*h[it]});
// cout<<it<<" !!\n";
// cout<<"pre "; for (int j=1; j<=n; j++) cout<<pre.qry(1,1,n,j)<<' '; cout<<'\n';
// cout<<"suf "; for (int j=1; j<=n; j++) cout<<suf.qry(1,1,n,j)<<' '; cout<<'\n';
// cout<<"----\n";
}
vector <long long> rres;
for (int i=1; i<=q; i++) rres.push_back(res[i]);
return rres;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
}