oj.uz

Submission #94667

# Submission time Handle Problem Language Result Execution time Memory
94667 2019-01-22T12:00:42 Z jangwonyoung Meetings (IOI18_meetings) C++14
100 / 100
 4296 ms 314448 KB 
#include "meetings.h"
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
bool debug=false;
const int N=750001,Q=750001;
int n,q;
ll h[N];
int ql[Q],qr[Q];
int rt=0;
int lc[N],rc[N];
int l[N],r[N];
int rmq[Q];
//build tree + rmq
vector<int>qp[N];
stack<int>s;
int par[N];
bool col[N];
int find(int x){
	if(par[x]!=x) par[x]=find(par[x]);
	return par[x];
}
void join(int x,int y){
	par[find(x)]=find(y);
}
void dfs(int id){
	l[id]=r[id]=id;
	par[id]=id;
	if(lc[id]!=0){
		dfs(lc[id]);
		l[id]=l[lc[id]];
		join(lc[id],id);
	}
	if(rc[id]!=0){
		dfs(rc[id]);
		r[id]=r[rc[id]];
		join(rc[id],id);
	}
	col[id]=true;
	for(auto cur:qp[id]){
		int newi=ql[cur]^qr[cur]^id;
		if(col[newi]) rmq[cur]=find(newi);
	}
}
//segtree
const int ts=1<<21;
bool llz[ts],rlz[ts];
ll tlonl[ts],tronl[ts];
ll tlc[ts],tlx[ts],trc[ts],trx[ts],tla[ts],tra[ts];
bool *lz;
ll *c,*x,*onl,*add;
void setl(){lz=llz,c=tlc,x=tlx,onl=tlonl;add=tla;};
void setr(){lz=rlz,c=trc,x=trx,onl=tronl;add=tra;};
void push(int id,int l,int r){
	if(add[id]>0){
		if(lz[id*2]) c[id*2]+=add[id];
		else add[id*2]+=add[id];
		if(lz[id*2+1]) c[id*2+1]+=add[id];
		else add[id*2+1]+=add[id];
		onl[id*2]+=add[id];
		onl[id*2+1]+=add[id];
		add[id]=0;
		return;
	}
	if(!lz[id]) return;
	int mid=(l+r)/2;
	c[id*2]=c[id];
	c[id*2+1]=c[id]+(mid-l+1)*x[id];
	x[id*2]=x[id*2+1]=x[id];
	onl[id*2]=c[id*2],onl[id*2+1]=c[id*2+1];
	add[id*2]=add[id*2+1]=0;
	lz[id*2]=lz[id*2+1]=true;
	lz[id]=false;
}
void pull(int id,int l,int r){
	onl[id]=onl[id*2];
}
void upd(int id,int l,int r,int ql,int qr,ll x0,ll x1){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		lz[id]=true;
		onl[id]=c[id]=x0+l*x1;
		add[id]=0;
		x[id]=x1;
		return;
	}
	push(id,l,r);
	int mid=(l+r)/2;
	upd(id*2,l,mid,ql,qr,x0,x1);
	upd(id*2+1,mid+1,r,ql,qr,x0,x1);
	pull(id,l,r);
}
void radd(int id,int l,int r,int ql,int qr,ll x){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		if(lz[id]) c[id]+=x;
		else add[id]+=x;
		onl[id]+=x;
		return;
	}
	push(id,l,r);
	int mid=(l+r)/2;
	radd(id*2,l,mid,ql,qr,x);
	radd(id*2+1,mid+1,r,ql,qr,x);
	pull(id,l,r);
}
ll getv(int id,int l,int r,int p){
	if(l==p) return onl[id];
	push(id,l,r);
	int mid=(l+r)/2;
	if(p<=mid) return getv(id*2,l,mid,p);
	else return getv(id*2+1,mid+1,r,p);
}
int findl(int id,int l,int r,int ql,int qr,ll x0,ll x1){
	if(l==r) return l+1;
	push(id,l,r);
	int mid=(l+r)/2;
	int cur=mid+1;
	if(cur>qr) return findl(id*2,l,mid,ql,qr,x0,x1);
	else if(cur<ql) return findl(id*2+1,cur,r,ql,qr,x0,x1);
	ll val=x0+x1*cur;
	if(val<=onl[id*2+1]) return findl(id*2,l,mid,ql,qr,x0,x1);
	else return findl(id*2+1,cur,r,ql,qr,x0,x1);
}
int findr(int id,int l,int r,int ql,int qr,ll x0,ll x1){
	if(l==r) return l;
	push(id,l,r);
	int mid=(l+r)/2;
	int cur=mid+1;
	if(cur>qr) return findr(id*2,l,mid,ql,qr,x0,x1);
	else if(cur<ql) return findr(id*2+1,cur,r,ql,qr,x0,x1);
	ll val=x0+x1*cur;
	if(val>onl[id*2+1]) return findr(id*2,l,mid,ql,qr,x0,x1);
	else return findr(id*2+1,cur,r,ql,qr,x0,x1);
}
//solve
vector<int>get[N];
ll ans[Q],ans2[Q];
ll fk(ll temp){
	if(temp>=(ll)1e18) return -1;
	else return temp;
}
int rnd;
void solve(int id){
	if(lc[id]!=0) solve(lc[id]);
	if(rc[id]!=0) solve(rc[id]);
	for(auto cur:get[id]){
		ans[cur]=h[id]*(qr[cur]-ql[cur]+1);//x==id
		if(qr[cur]!=id){//x<id
			setl();
			ans[cur]=min(ans[cur],h[id]*(id-ql[cur]+1)+getv(1,0,n,qr[cur]));
		}
		if(ql[cur]!=id){//x>id
			setr();
			ans[cur]=min(ans[cur],h[id]*(qr[cur]-id+1)+getv(1,0,n,ql[cur]));
		}
	}
	ll val,x0,x1;
	setl();
	if(l[id]!=id) val=getv(1,0,n,id-1)+h[id];
	else val=h[id];
	x1=h[id];
	x0=val-id*x1;
	radd(1,0,n,id,r[id],h[id]*(id-l[id]+1));
	int pos=findr(1,0,n,id,r[id],x0,x1);
	upd(1,0,n,id,pos,x0,x1);
	setr();
	if(r[id]!=id) val=getv(1,0,n,id+1)+h[id];
	else val=h[id];
	x1=-h[id];
	x0=val-id*x1;
	radd(1,0,n,l[id],id,h[id]*(r[id]-id+1));
	pos=findl(1,0,n,l[id],id,x0,x1);
	upd(1,0,n,pos,id,x0,x1);
	
}
vector<ll> minimum_costs(vector<int> H,vector<int> L,vector<int> R) {
	n=H.size(),q=L.size();
	for(int i=1; i<=n ;i++) h[i]=H[i-1];
	for(int i=1; i<=q ;i++) ql[i]=L[i-1]+1,qr[i]=R[i-1]+1;
	for(int i=1; i<=n ;i++){
		int last=0;
		while(!s.empty() && h[s.top()]<h[i]){
			last=s.top();
			s.pop();
		}
		if(!s.empty()) rc[s.top()]=i;
		else rt=i;
		lc[i]=last;
		s.push(i);
	}
	for(int i=1; i<=q ;i++){
		qp[ql[i]].push_back(i);
		qp[qr[i]].push_back(i);
	}
	dfs(rt);
	for(int i=1; i<=q ;i++) get[rmq[i]].push_back(i);
	setl();
	upd(1,0,n,1,n,1e18,0);
	setr();
	upd(1,0,n,1,n,1e18,0);
	solve(rt);
	vector<ll>ret(q);
	for(int i=1; i<=q ;i++) ret[i-1]=ans[i];
	return ret;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35720 KB Output is correct
2 Correct 40 ms 36344 KB Output is correct
3 Correct 41 ms 36292 KB Output is correct
4 Correct 41 ms 36352 KB Output is correct
5 Correct 41 ms 36384 KB Output is correct
6 Correct 41 ms 36412 KB Output is correct
7 Correct 40 ms 36320 KB Output is correct
8 Correct 41 ms 36524 KB Output is correct
9 Correct 41 ms 36440 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35720 KB Output is correct
2 Correct 40 ms 36344 KB Output is correct
3 Correct 41 ms 36292 KB Output is correct
4 Correct 41 ms 36352 KB Output is correct
5 Correct 41 ms 36384 KB Output is correct
6 Correct 41 ms 36412 KB Output is correct
7 Correct 40 ms 36320 KB Output is correct
8 Correct 41 ms 36524 KB Output is correct
9 Correct 41 ms 36440 KB Output is correct
10 Correct 49 ms 37496 KB Output is correct
11 Correct 48 ms 37368 KB Output is correct
12 Correct 50 ms 37420 KB Output is correct
13 Correct 48 ms 37340 KB Output is correct
14 Correct 48 ms 37648 KB Output is correct
15 Correct 50 ms 37396 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35756 KB Output is correct
2 Correct 95 ms 40540 KB Output is correct
3 Correct 444 ms 67900 KB Output is correct
4 Correct 424 ms 64044 KB Output is correct
5 Correct 391 ms 70236 KB Output is correct
6 Correct 431 ms 70188 KB Output is correct
7 Correct 493 ms 69760 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35756 KB Output is correct
2 Correct 95 ms 40540 KB Output is correct
3 Correct 444 ms 67900 KB Output is correct
4 Correct 424 ms 64044 KB Output is correct
5 Correct 391 ms 70236 KB Output is correct
6 Correct 431 ms 70188 KB Output is correct
7 Correct 493 ms 69760 KB Output is correct
8 Correct 424 ms 64316 KB Output is correct
9 Correct 336 ms 62728 KB Output is correct
10 Correct 406 ms 64788 KB Output is correct
11 Correct 415 ms 63960 KB Output is correct
12 Correct 330 ms 62272 KB Output is correct
13 Correct 393 ms 64432 KB Output is correct
14 Correct 452 ms 67900 KB Output is correct
15 Correct 416 ms 63924 KB Output is correct
16 Correct 468 ms 67912 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35720 KB Output is correct
2 Correct 40 ms 36344 KB Output is correct
3 Correct 41 ms 36292 KB Output is correct
4 Correct 41 ms 36352 KB Output is correct
5 Correct 41 ms 36384 KB Output is correct
6 Correct 41 ms 36412 KB Output is correct
7 Correct 40 ms 36320 KB Output is correct
8 Correct 41 ms 36524 KB Output is correct
9 Correct 41 ms 36440 KB Output is correct
10 Correct 49 ms 37496 KB Output is correct
11 Correct 48 ms 37368 KB Output is correct
12 Correct 50 ms 37420 KB Output is correct
13 Correct 48 ms 37340 KB Output is correct
14 Correct 48 ms 37648 KB Output is correct
15 Correct 50 ms 37396 KB Output is correct
16 Correct 34 ms 35756 KB Output is correct
17 Correct 95 ms 40540 KB Output is correct
18 Correct 444 ms 67900 KB Output is correct
19 Correct 424 ms 64044 KB Output is correct
20 Correct 391 ms 70236 KB Output is correct
21 Correct 431 ms 70188 KB Output is correct
22 Correct 493 ms 69760 KB Output is correct
23 Correct 424 ms 64316 KB Output is correct
24 Correct 336 ms 62728 KB Output is correct
25 Correct 406 ms 64788 KB Output is correct
26 Correct 415 ms 63960 KB Output is correct
27 Correct 330 ms 62272 KB Output is correct
28 Correct 393 ms 64432 KB Output is correct
29 Correct 452 ms 67900 KB Output is correct
30 Correct 416 ms 63924 KB Output is correct
31 Correct 468 ms 67912 KB Output is correct
32 Correct 3793 ms 257704 KB Output is correct
33 Correct 2638 ms 246224 KB Output is correct
34 Correct 3452 ms 260164 KB Output is correct
35 Correct 3832 ms 258960 KB Output is correct
36 Correct 2651 ms 246752 KB Output is correct
37 Correct 3425 ms 260356 KB Output is correct
38 Correct 4227 ms 288956 KB Output is correct
39 Correct 3908 ms 288956 KB Output is correct
40 Correct 4081 ms 262320 KB Output is correct
41 Correct 3920 ms 310636 KB Output is correct
42 Correct 4275 ms 314448 KB Output is correct
43 Correct 4244 ms 314392 KB Output is correct
44 Correct 4296 ms 287024 KB Output is correct