Submission #558711

#	Time	Username	Problem	Language	Result	Execution time	Memory
558711		jamezzz	Meetings (IOI18_meetings)	C++17	100 / 100	3032 ms	386092 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> line;
typedef pair<int,int> ii;
#define fi first
#define se second
#define lc 2*i+1
#define rc 2*i+2
#define pb push_back
#define LINF 1023456789123456789

#define pf printf

#define maxn 750005

int n,q;
vector<int> h;
vector<ll> ans;

struct query{
	int l,r,i;
};
vector<query> qrys[maxn];

ll eval(line l,ll x){
	return l.fi*x+l.se;
}

struct seg{
	ii v[maxn*4];
	void init(int i,int s,int e){
		if(s==e){v[i]={h[s],s};return;}
		int m=(s+e)>>1;
		init(lc,s,m);
		init(rc,m+1,e);
		v[i]=max(v[lc],v[rc]);
	}
	void init(){
		init(0,0,n-1);
	}
	ii qry(int i,int s,int e,int x,int y){
		if(s==x&&e==y)return v[i];
		int m=(s+e)>>1;
		if(y<=m)return qry(lc,s,m,x,y);
		if(x>m)return qry(rc,m+1,e,x,y);
		return max(qry(lc,s,m,x,m),qry(rc,m+1,e,m+1,y));
	}
	int qry(int x,int y){
		return qry(0,0,n-1,x,y).se;
	}
}maxseg;

struct lichao{
	int s,e,m;
	lichao *l,*r;
	line val={0,LINF};
	ll lz=0;
	
	lichao(int _s,int _e){
		s=_s;e=_e;m=(s+e)>>1;
		if(s!=e){
			l=new lichao(s,m);
			r=new lichao(m+1,e);
		}
	}
	void ppo(){
		val.se+=lz;
		if(s!=e)l->lz+=lz,r->lz+=lz;
		lz=0;
	}
	void insert(int x,int y,line v){
		if(x>y)return;
		ppo();
		if(s==x&&e==y){
			if(eval(v,m)<eval(val,m))swap(v,val);
			if(s==e)return;
			if(eval(v,s)>=eval(val,s)&&eval(v,e)>=eval(val,e))return;
			if(eval(v,s)<eval(val,s))l->insert(x,m,v);
			else r->insert(m+1,y,v);
		}
		if(y<=m)l->insert(x,y,v);
		else if(x>m)r->insert(x,y,v);
		else l->insert(x,m,v),r->insert(m+1,y,v);
	}
	void add(int x,int y,ll v){
		if(x>y)return;
		if(s==x&&e==y){lz+=v;return;}
		if(y<=m)l->add(x,y,v);
		else if(x>m)r->add(x,y,v);
		else l->add(x,m,v),r->add(m+1,y,v);
	}
	ll qry(int x){
		ppo();
		if(s==x&&e==x)return eval(val,x);
		if(x<=m)return min(eval(val,x),l->qry(x));
		else return min(eval(val,x),r->qry(x));
	}
}*llct,*rlct;

void solve(int l,int r){
	if(l>r)return;
	int m=maxseg.qry(l,r);
	solve(l,m-1);
	solve(m+1,r);
	
	llct->insert(m,m,{0,0});
	rlct->insert(m,m,{0,0});
	
	for(query &q:qrys[m]){
		ans[q.i]=min(llct->qry(q.l)+(ll)(q.r-m+1)*h[m],
					 rlct->qry(q.r)+(ll)(m-q.l+1)*h[m]);
	}
	
	llct->add(l,m,(ll)(r-m+1)*h[m]);
	llct->insert(l,m,{-h[m],(ll)(m+1)*h[m]+(m==r?0:llct->qry(m+1))});
	
	rlct->add(m,r,(ll)(m-l+1)*h[m]);
	rlct->insert(m,r,{h[m],(ll)(1-m)*h[m]+(l==m?0:rlct->qry(m-1))});
}

vector<ll> minimum_costs(vector<int> _h,vector<int> l,vector<int> r){
	n=_h.size();
	q=l.size();
	h=_h;
	maxseg.init();
	
	ans.resize(q);
	for(int i=0;i<q;++i){
		int m=maxseg.qry(l[i],r[i]);
		qrys[m].pb({l[i],r[i],i});
	}
	
	llct=new lichao(0,n-1);
	rlct=new lichao(0,n-1);
	solve(0,n-1);
	
	return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40