oj.uz

Submission #836542

# Submission time Handle Problem Language Result Execution time Memory
836542 2023-08-24T12:37:32 Z arnold518 Meetings (IOI18_meetings) C++17
100 / 100
 3072 ms 407516 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 129484 KB Output is correct
2 Correct 48 ms 129796 KB Output is correct
3 Correct 49 ms 129776 KB Output is correct
4 Correct 49 ms 129720 KB Output is correct
5 Correct 48 ms 129796 KB Output is correct
6 Correct 47 ms 129996 KB Output is correct
7 Correct 54 ms 129808 KB Output is correct
8 Correct 49 ms 130144 KB Output is correct
9 Correct 50 ms 129928 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 129484 KB Output is correct
2 Correct 48 ms 129796 KB Output is correct
3 Correct 49 ms 129776 KB Output is correct
4 Correct 49 ms 129720 KB Output is correct
5 Correct 48 ms 129796 KB Output is correct
6 Correct 47 ms 129996 KB Output is correct
7 Correct 54 ms 129808 KB Output is correct
8 Correct 49 ms 130144 KB Output is correct
9 Correct 50 ms 129928 KB Output is correct
10 Correct 55 ms 130764 KB Output is correct
11 Correct 54 ms 130628 KB Output is correct
12 Correct 57 ms 130780 KB Output is correct
13 Correct 54 ms 130624 KB Output is correct
14 Correct 60 ms 131136 KB Output is correct
15 Correct 55 ms 130588 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 129456 KB Output is correct
2 Correct 98 ms 135656 KB Output is correct
3 Correct 299 ms 157884 KB Output is correct
4 Correct 291 ms 150108 KB Output is correct
5 Correct 226 ms 153892 KB Output is correct
6 Correct 277 ms 159428 KB Output is correct
7 Correct 309 ms 161352 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 129456 KB Output is correct
2 Correct 98 ms 135656 KB Output is correct
3 Correct 299 ms 157884 KB Output is correct
4 Correct 291 ms 150108 KB Output is correct
5 Correct 226 ms 153892 KB Output is correct
6 Correct 277 ms 159428 KB Output is correct
7 Correct 309 ms 161352 KB Output is correct
8 Correct 302 ms 150756 KB Output is correct
9 Correct 259 ms 150456 KB Output is correct
10 Correct 285 ms 150904 KB Output is correct
11 Correct 285 ms 149908 KB Output is correct
12 Correct 259 ms 149524 KB Output is correct
13 Correct 279 ms 150440 KB Output is correct
14 Correct 293 ms 158020 KB Output is correct
15 Correct 284 ms 149908 KB Output is correct
16 Correct 301 ms 157820 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 129484 KB Output is correct
2 Correct 48 ms 129796 KB Output is correct
3 Correct 49 ms 129776 KB Output is correct
4 Correct 49 ms 129720 KB Output is correct
5 Correct 48 ms 129796 KB Output is correct
6 Correct 47 ms 129996 KB Output is correct
7 Correct 54 ms 129808 KB Output is correct
8 Correct 49 ms 130144 KB Output is correct
9 Correct 50 ms 129928 KB Output is correct
10 Correct 55 ms 130764 KB Output is correct
11 Correct 54 ms 130628 KB Output is correct
12 Correct 57 ms 130780 KB Output is correct
13 Correct 54 ms 130624 KB Output is correct
14 Correct 60 ms 131136 KB Output is correct
15 Correct 55 ms 130588 KB Output is correct
16 Correct 47 ms 129456 KB Output is correct
17 Correct 98 ms 135656 KB Output is correct
18 Correct 299 ms 157884 KB Output is correct
19 Correct 291 ms 150108 KB Output is correct
20 Correct 226 ms 153892 KB Output is correct
21 Correct 277 ms 159428 KB Output is correct
22 Correct 309 ms 161352 KB Output is correct
23 Correct 302 ms 150756 KB Output is correct
24 Correct 259 ms 150456 KB Output is correct
25 Correct 285 ms 150904 KB Output is correct
26 Correct 285 ms 149908 KB Output is correct
27 Correct 259 ms 149524 KB Output is correct
28 Correct 279 ms 150440 KB Output is correct
29 Correct 293 ms 158020 KB Output is correct
30 Correct 284 ms 149908 KB Output is correct
31 Correct 301 ms 157820 KB Output is correct
32 Correct 2456 ms 292724 KB Output is correct
33 Correct 1887 ms 287608 KB Output is correct
34 Correct 2376 ms 294748 KB Output is correct
35 Correct 2575 ms 293312 KB Output is correct
36 Correct 1889 ms 292240 KB Output is correct
37 Correct 2278 ms 295160 KB Output is correct
38 Correct 2837 ms 354172 KB Output is correct
39 Correct 2864 ms 354124 KB Output is correct
40 Correct 2771 ms 301632 KB Output is correct
41 Correct 2689 ms 404680 KB Output is correct
42 Correct 3016 ms 407516 KB Output is correct
43 Correct 3027 ms 407400 KB Output is correct
44 Correct 3072 ms 353540 KB Output is correct