Submission #836542

#	Time	Username	Problem	Language	Result	Execution time	Memory
836542		arnold518	Meetings (IOI18_meetings)	C++17	100 / 100	3072 ms	407516 KiB

meetings

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 75e4;
const ll INF = 1e18;

int N, Q;
ll A[MAXN+10];
pii B[MAXN+10];
ll ans[MAXN+10], ans1[MAXN+10], ans2[MAXN+10];

struct SEG
{
	pll tree[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node]={A[tl], tl};
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
	pll query(int node, int tl, int tr, int l, int r)
	{
		if(r<tl || tr<l) return pll(0, 0);
		if(l<=tl && tr<=r) return tree[node];
		int mid=tl+tr>>1;
		return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
}seg;

struct LiChao
{
	pll tree[MAXN*4+10];
	ll lazy[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		tree[node]=pll(0, INF);
		lazy[node]=0;
		if(tl==tr) return;
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
	}
	void busy(int node, int tl, int tr)
	{
		tree[node].second+=lazy[node];
		if(tl!=tr)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	ll query(int node, int tl, int tr, int x)
	{
		busy(node, tl, tr);
		ll ret=tree[node].first*x+tree[node].second;
		if(tl==tr) return ret;
		int mid=tl+tr>>1;
		if(x<=mid) ret=min(ret, query(node*2, tl, mid, x));
		else ret=min(ret, query(node*2+1, mid+1, tr, x));
		return ret;
	}
	void update(int node, int tl, int tr, int l, int r, ll k)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r)
		{
			lazy[node]+=k;
			busy(node, tl, tr);
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
	}
	void update2(int node, int tl, int tr, pll p)
	{
		busy(node, tl, tr);
		ll fl=tree[node].first*tl+tree[node].second, fr=tree[node].first*tr+tree[node].second;
		ll nfl=p.first*tl+p.second, nfr=p.first*tr+p.second;
		if(fl<=nfl && fr<=nfr) return;
		if(nfl<=fl && nfr<=fr) { tree[node]=p; return; }
		int mid=tl+tr>>1;
		update2(node*2, tl, mid, p);
		update2(node*2+1, mid+1, tr, p);
	}
	void update1(int node, int tl, int tr, int l, int r, pll p)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r)
		{
			update2(node, tl, tr, p);
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update1(node*2, tl, mid, l, r, p);
		update1(node*2+1, mid+1, tr, l, r, p);
	}
}lct1, lct2;

vector<pii> LV[MAXN+10], RV[MAXN+10];

void solve(int l, int r)
{
	if(l>r) return;
	pll t=seg.query(1, 1, N, l, r);
	int mid=t.second;

	solve(l, mid-1);
	solve(mid+1, r);

	ll val;
	if(l<=mid-1) val=lct1.query(1, 1, N, mid-1)+A[mid];
	else val=A[mid];
	lct1.update1(1, 1, N, mid, mid, pll(0, val));
	lct1.update(1, 1, N, mid+1, r, A[mid]*(mid-l+1));
	lct1.update1(1, 1, N, mid+1, r, pll(A[mid], -A[mid]*mid+val));

	if(mid+1<=r) val=lct2.query(1, 1, N, mid+1)+A[mid];
	else val=A[mid];
	lct2.update1(1, 1, N, mid, mid, pll(0, val));
	lct2.update(1, 1, N, l, mid-1, A[mid]*(r-mid+1));
	lct2.update1(1, 1, N, l, mid-1, pll(-A[mid], A[mid]*mid+val));

	while(!LV[l].empty() && LV[l].back().first<=r)
	{
		int t=LV[l].back().second;
		ans1[t]=lct1.query(1, 1, N, LV[l].back().first);
		LV[l].pop_back();
	}
	while(!RV[r].empty() && RV[r].back().first>=l)
	{
		int t=RV[r].back().second;
		ans2[t]=lct2.query(1, 1, N, RV[r].back().first);
		RV[r].pop_back();
	}
	//printf("solve %d %d\n", l, r);
	//for(int i=l; i<=r; i++) printf("%lld ", lct1.query(1, 1, N, i)); printf("\n");
	//for(int i=l; i<=r; i++) printf("%lld ", lct2.query(1, 1, N, i)); printf("\n");
}

vector<ll> ret;
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++) A[i]=_H[i-1];
	for(int i=1; i<=Q; i++) B[i]={_L[i-1]+1, _R[i-1]+1};

	seg.init(1, 1, N);

	for(int i=1; i<=Q; i++)
	{
		auto [l, r] = B[i];
		ans[i]=INF;
		
		int t=seg.query(1, 1, N, l, r).second;
		if(l==r) ans[i]=A[l];

		if(t+1<=r) LV[t+1].push_back({r, i});
		if(l<=t-1) RV[t-1].push_back({l, i});
	}
	for(int i=1; i<=N; i++)
	{
		sort(LV[i].begin(), LV[i].end(), greater<pii>());
		sort(RV[i].begin(), RV[i].end());
		//for(auto it : LV[i]) printf("%d %d / ", it.first, it.second); printf(" : %d\n", i);
		//for(auto it : RV[i]) printf("%d %d / ", it.first, it.second); printf(" : %d\n", i);
	}

	lct1.init(1, 1, N); lct2.init(1, 1, N);
	solve(1, N);

	for(int i=1; i<=Q; i++)
	{
		auto [l, r] = B[i];
		int t=seg.query(1, 1, N, l, r).second;
		ans[i]=min(ans[i], ans1[i]+(t-l+1)*A[t]);
		ans[i]=min(ans[i], ans2[i]+(r-t+1)*A[t]);
	}

	for(int i=1; i<=Q; i++) ret.push_back(ans[i]);
	return ret;
}

Compilation message (stderr)

meetings.cpp: In member function 'void SEG::init(int, int, int)':
meetings.cpp:27:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int mid=tl+tr>>1;
      |           ~~^~~
meetings.cpp: In member function 'pll SEG::query(int, int, int, int, int)':
meetings.cpp:36:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid=tl+tr>>1;
      |           ~~^~~
meetings.cpp: In member function 'void LiChao::init(int, int, int)':
meetings.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int mid=tl+tr>>1;
      |           ~~^~~
meetings.cpp: In member function 'll LiChao::query(int, int, int, int)':
meetings.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int mid=tl+tr>>1;
      |           ~~^~~
meetings.cpp: In member function 'void LiChao::update(int, int, int, int, int, ll)':
meetings.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   int mid=tl+tr>>1;
      |           ~~^~~
meetings.cpp: In member function 'void LiChao::update2(int, int, int, pll)':
meetings.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |   int mid=tl+tr>>1;
      |           ~~^~~
meetings.cpp: In member function 'void LiChao::update1(int, int, int, int, int, pll)':
meetings.cpp:108:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |   int mid=tl+tr>>1;
      |           ~~^~~

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