Submission #132752

#	Time	Username	Problem	Language	Result	Execution time	Memory
132752		TadijaSebez	Meetings (IOI18_meetings)	C++11	100 / 100	3378 ms	301240 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=750050;
const int M=2*N;
const ll inf=1e18;
int n,q;
int l[N],r[N],h[N];
ll ans[N];
struct LiChaoSegmentTree
{
	struct Line
	{
		ll k,n;
		Line(){ k=n=0;}
		Line(ll a, ll b):k(a),n(b){}
		ll Get(ll x){ return k*x+n;}
	} line[M];
	int ls[M],rs[M],tsz,root;
	ll lzy[M];
	LiChaoSegmentTree(){}
	void Build(int &c, int ss, int se)
	{
		c=++tsz;lzy[c]=0;line[c]=Line(0,inf);
		if(ss==se){ line[c]=Line();return;}
		int mid=ss+se>>1;
		Build(ls[c],ss,mid);
		Build(rs[c],mid+1,se);
	}
	void Build(){ Build(root,1,n);}
	void upd(int c, ll f)
	{
		line[c].n+=f;
		lzy[c]+=f;
	}
	void push(int c)
	{
		if(lzy[c])
		{
			upd(ls[c],lzy[c]);
			upd(rs[c],lzy[c]);
			lzy[c]=0;
		}
	}
	void Add(int c, int ss, int se, int qs, int qe, ll f)
	{
		if(qs>qe || qs>se || ss>qe) return;
		if(qs<=ss && qe>=se){ upd(c,f);return;}
		push(c);
		int mid=ss+se>>1;
		Add(ls[c],ss,mid,qs,qe,f);
		Add(rs[c],mid+1,se,qs,qe,f);
	}
	void Add(int l, int r, ll f){ Add(root,1,n,l,r,f);}
	void Set(int c, int ss, int se, int qs, int qe, Line k)
	{
        if(qs>qe || qs>se || ss>qe) return;
        if(qs<=ss && qe>=se)
		{
			ll A=k.Get(ss),B=line[c].Get(ss),C=k.Get(se),D=line[c].Get(se);
			if(A<=B && C<=D){ line[c]=k;return;}
			if(A>=B && C>=D) return;
			push(c);
			int mid=ss+se>>1;
			if(A<=B) swap(line[c],k);
			if(line[c].Get(mid)<=k.Get(mid)) Set(rs[c],mid+1,se,qs,qe,k);
			else swap(line[c],k),Set(ls[c],ss,mid,qs,qe,k);
			return;
		}
		push(c);
		int mid=ss+se>>1;
		Set(ls[c],ss,mid,qs,qe,k);
		Set(rs[c],mid+1,se,qs,qe,k);
	}
	void Set(int l, int r, ll b, ll a){ Set(root,1,n,l,r,Line(a,b));}
	ll Get(int c, int ss, int se, int qi)
	{
		ll ans=line[c].Get(qi);
		if(ss==se) return ans;
		push(c);
		int mid=ss+se>>1;
		if(qi<=mid) return min(ans,Get(ls[c],ss,mid,qi));
		else return min(ans,Get(rs[c],mid+1,se,qi));
	}
	ll Get(int qi){ return Get(root,1,n,qi);}
} FW,BW;
struct SegmentTree
{
	int mx[M];
	void init(){ for(int i=1;i<M;i++) mx[i]=0;}
	int my_max(int x, int y){ return mp(h[x],x)>mp(h[y],y)?x:y;}
	void Build()
	{
		for(int i=n+N;i>=N;i--) mx[i]=i-N;
		for(int i=N-1;i;i--) mx[i]=my_max(mx[i<<1],mx[i<<1|1]);
	}
	int Get(int l, int r)
	{
		int ans=0;
		for(l+=N,r+=N;l<=r;l>>=1,r>>=1)
		{
			if(l%2==1) ans=my_max(ans,mx[l++]);
			if(r%2==0) ans=my_max(ans,mx[r--]);
		}
		return ans;
	}
} RMQ;
vector<int> Qs[N];
void Solve(int l, int r)
{
	if(l>r) return;
    int m=RMQ.Get(l,r);
    Solve(l,m-1);Solve(m+1,r);
    for(int i:Qs[m]) ans[i]=min(FW.Get(::r[i])+(ll)h[m]*(m-::l[i]+1),BW.Get(::l[i])+(ll)h[m]*(::r[i]-m+1));
    FW.Add(m,r,(ll)h[m]*(m-l+1));
    if(m!=l) FW.Set(m,r,FW.Get(m-1)-(ll)h[m]*(m-1),h[m]);
    BW.Add(l,m,(ll)h[m]*(r-m+1));
    if(m!=r) BW.Set(l,m,BW.Get(m+1)+(ll)h[m]*(m+1),-h[m]);
}
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++) l[i]=L[i-1]+1,r[i]=R[i-1]+1;
	RMQ.Build();
	for(int i=1;i<=q;i++) Qs[RMQ.Get(l[i],r[i])].pb(i);
	FW.Build();BW.Build();
	Solve(1,n);
	vector<ll> ret;
	for(int i=1;i<=q;i++) ret.pb(ans[i]);
	return ret;
}

Compilation message (stderr)

meetings.cpp: In member function 'void LiChaoSegmentTree::Build(int&, int, int)':
meetings.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
meetings.cpp: In member function 'void LiChaoSegmentTree::Add(int, int, int, int, int, long long int)':
meetings.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
meetings.cpp: In member function 'void LiChaoSegmentTree::Set(int, int, int, int, int, LiChaoSegmentTree::Line)':
meetings.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=ss+se>>1;
            ~~^~~
meetings.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
meetings.cpp: In member function 'long long int LiChaoSegmentTree::Get(int, int, int, int)':
meetings.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~

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