oj.uz

Submission #795107

# Submission time Handle Problem Language Result Execution time Memory
795107 2023-07-27T06:38:51 Z ymm Meetings (IOI18_meetings) C++17
100 / 100
 2441 ms 479456 KB 
#include "meetings.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1e6+10;

ll eval(const pll &f, ll x) { return f.first * x + f.second; }

namespace seg {
	struct node {
		pll val;
		ll lzy;
		ll fst, lst;
		bool leaf;
	} t[N*4];
	int sz;

	void init(int n) {
		sz = n;
		t[0].val = {};
		t[0].lzy = 0;
		t[0].fst = 0;
		t[0].lst = 0;
		t[0].leaf = 1;
	}

	void up(int i, ll x) {
		t[i].val.second += x;
		t[i].lzy += x;
		t[i].fst += x;
		t[i].lst += x;
	}
	void ppg(int i, int b, int e) {
		if (t[i].leaf) {
			t[2*i+1] = t[2*i+2] = t[i];
			t[2*i+1].lst = eval(t[2*i+1].val, (b+e)/2-1);
			t[2*i+2].fst = eval(t[2*i+2].val, (b+e)/2);
			t[i].leaf = 0;
		} else {
			up(2*i+1, t[i].lzy);
			up(2*i+2, t[i].lzy);
		}
		t[i].lzy = 0;
	}

	void merge(int i) {
		t[i].fst = t[2*i+1].fst;
		t[i].lst = t[2*i+2].lst;
	}

	void add(int l, int r, ll x, int i, int b, int e) {
		if (l <= b && e <= r) {
			up(i, x);
			return;
		}
		ppg(i, b, e);
		if (l < (b+e)/2)
			add(l, r, x, 2*i+1, b, (b+e)/2);
		if ((b+e)/2 < r)
			add(l, r, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void add(int l, int r, ll x) { add(l, r, x, 0, 0, sz); }

	void mn(int l, int r, pll f, int i, int b, int e) {
		ll fst2 = eval(f, b);
		ll lst2 = eval(f, e-1);
		if (l <= b && e <= r && t[i].fst >= fst2 && t[i].lst >= lst2) {
			t[i].val = f;
			t[i].fst = fst2;
			t[i].lst = lst2;
			t[i].leaf = 1;
			return;
		}
		if (l <= b && e <= r && t[i].lst <= lst2 && t[i].fst <= fst2)
			return;
		ppg(i, b, e);
		if (l < (b+e)/2)
			mn(l, r, f, 2*i+1, b, (b+e)/2);
		if ((b+e)/2 < r)
			mn(l, r, f, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void mn(int l, int r, pll f) { mn(l, r, f, 0, 0, sz); }

	ll get(int p, int i, int b, int e) {
		if (t[i].leaf)
			return eval(t[i].val, p);
		ppg(i, b, e);
		if (p < (b+e)/2)
			return get(p, 2*i+1, b, (b+e)/2);
		else
			return get(p, 2*i+2, (b+e)/2, e);
	}
	ll get(int p) { return get(p, 0, 0, sz); }
}

namespace rmq {
	const int lg = 20;
	pii mx[lg][N];

	void make(vector<int> a) {
		int n = a.size();
		Loop (i,0,n)
			mx[0][i] = {a[i], i};
		Loop (i,0,lg-1) {
			for (int j = 0; j + (2 << i) <= n; ++j)
				mx[i+1][j] = max(mx[i][j], mx[i][j+(1<<i)]);
		}
	}

	pii get(int l, int r) {
		int k = __lg(r-l);
		return max(mx[k][l], mx[k][r-(1<<k)]);
	}
}

ll arr[N];

namespace cart {
	pii t[N];
	vector<pair<ll *, int>> queryl[N];
	vector<pair<ll *, int>> queryr[N];
	int rt;
	int sz;

	void make(int &ans, int l, int r) {
		if (l >= r) {
			ans = -1;
			return;
		}
		ans = rmq::get(l, r).second;
		make(t[ans].first, l, ans);
		make(t[ans].second, ans+1, r);
	}
	void make(int n) { sz = n; make(rt, 0, sz); }

	void dfs(int v, int l, int r, void (*merge)(int, int, int)) {
		if (v == -1)
			return;
		dfs(t[v].first, l, v, merge);
		dfs(t[v].second, v+1, r, merge);
		merge(v, l, r);
	}

	void mergel(int v, int l, int r) {
		seg::add(v, r, (v-l+1)*arr[v]);
		if (v != l) {
			ll x = seg::get(v-1);
			seg::mn(v, r, pll{arr[v], x - (v-1)*arr[v]});
		}
		for (auto [p, pos] : queryl[v])
			*p = seg::get(pos);
	}
	void merger(int v, int l, int r) {
		seg::add(l, v+1, (r-v)*arr[v]);
		if (v != r-1) {
			ll x = seg::get(v+1);
			seg::mn(l, v+1, pll{-arr[v], x + (v+1)*arr[v]});
		}
		for (auto [p, pos] : queryr[v])
			*p = seg::get(pos);
	}

	void answer() {
		seg::init(sz);
		dfs(rt, 0, sz, mergel);
		seg::init(sz);
		dfs(rt, 0, sz, merger);
	}
}

ll Ql[N], Qr[N];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	int n = H.size();
	Loop (i,0,n)
		arr[i] = H[i];
	rmq::make(H);
	cart::make(n);
	int q = L.size();
	Loop (i,0,q) {
		int l = L[i];
		int r = R[i]+1;
		int v = rmq::get(l, r).second;
		if (l < v) {
			cart::queryr[cart::t[v].first]
				.push_back({&Ql[i], l});
		}
		if (v < r-1) {
			cart::queryl[cart::t[v].second]
				.push_back({&Qr[i], r-1});
		}
	}
	cart::answer();
	vector<ll> ans(q);
	Loop (i,0,q) {
		int l = L[i];
		int r = R[i]+1;
		int v = rmq::get(l, r).second;
		ans[i] = arr[v] * (r-l);
		if (l < v)
			ans[i] = min(ans[i], Ql[i] + arr[v] * (r-v));
		if (v < r-1)
			ans[i] = min(ans[i], Qr[i] + arr[v] * (v-l+1));
	}
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 235148 KB Output is correct
2 Correct 79 ms 235584 KB Output is correct
3 Correct 83 ms 235596 KB Output is correct
4 Correct 96 ms 235584 KB Output is correct
5 Correct 90 ms 235524 KB Output is correct
6 Correct 81 ms 235664 KB Output is correct
7 Correct 85 ms 235568 KB Output is correct
8 Correct 102 ms 235720 KB Output is correct
9 Correct 84 ms 235652 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 235148 KB Output is correct
2 Correct 79 ms 235584 KB Output is correct
3 Correct 83 ms 235596 KB Output is correct
4 Correct 96 ms 235584 KB Output is correct
5 Correct 90 ms 235524 KB Output is correct
6 Correct 81 ms 235664 KB Output is correct
7 Correct 85 ms 235568 KB Output is correct
8 Correct 102 ms 235720 KB Output is correct
9 Correct 84 ms 235652 KB Output is correct
10 Correct 108 ms 236360 KB Output is correct
11 Correct 97 ms 236340 KB Output is correct
12 Correct 85 ms 236328 KB Output is correct
13 Correct 85 ms 236440 KB Output is correct
14 Correct 94 ms 236548 KB Output is correct
15 Correct 99 ms 236324 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 235084 KB Output is correct
2 Correct 109 ms 240848 KB Output is correct
3 Correct 254 ms 262616 KB Output is correct
4 Correct 237 ms 260264 KB Output is correct
5 Correct 214 ms 257384 KB Output is correct
6 Correct 249 ms 262696 KB Output is correct
7 Correct 266 ms 263204 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 235084 KB Output is correct
2 Correct 109 ms 240848 KB Output is correct
3 Correct 254 ms 262616 KB Output is correct
4 Correct 237 ms 260264 KB Output is correct
5 Correct 214 ms 257384 KB Output is correct
6 Correct 249 ms 262696 KB Output is correct
7 Correct 266 ms 263204 KB Output is correct
8 Correct 269 ms 260688 KB Output is correct
9 Correct 257 ms 260516 KB Output is correct
10 Correct 266 ms 260880 KB Output is correct
11 Correct 246 ms 260232 KB Output is correct
12 Correct 237 ms 259964 KB Output is correct
13 Correct 342 ms 260984 KB Output is correct
14 Correct 272 ms 262784 KB Output is correct
15 Correct 230 ms 259844 KB Output is correct
16 Correct 260 ms 262312 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 235148 KB Output is correct
2 Correct 79 ms 235584 KB Output is correct
3 Correct 83 ms 235596 KB Output is correct
4 Correct 96 ms 235584 KB Output is correct
5 Correct 90 ms 235524 KB Output is correct
6 Correct 81 ms 235664 KB Output is correct
7 Correct 85 ms 235568 KB Output is correct
8 Correct 102 ms 235720 KB Output is correct
9 Correct 84 ms 235652 KB Output is correct
10 Correct 108 ms 236360 KB Output is correct
11 Correct 97 ms 236340 KB Output is correct
12 Correct 85 ms 236328 KB Output is correct
13 Correct 85 ms 236440 KB Output is correct
14 Correct 94 ms 236548 KB Output is correct
15 Correct 99 ms 236324 KB Output is correct
16 Correct 76 ms 235084 KB Output is correct
17 Correct 109 ms 240848 KB Output is correct
18 Correct 254 ms 262616 KB Output is correct
19 Correct 237 ms 260264 KB Output is correct
20 Correct 214 ms 257384 KB Output is correct
21 Correct 249 ms 262696 KB Output is correct
22 Correct 266 ms 263204 KB Output is correct
23 Correct 269 ms 260688 KB Output is correct
24 Correct 257 ms 260516 KB Output is correct
25 Correct 266 ms 260880 KB Output is correct
26 Correct 246 ms 260232 KB Output is correct
27 Correct 237 ms 259964 KB Output is correct
28 Correct 342 ms 260984 KB Output is correct
29 Correct 272 ms 262784 KB Output is correct
30 Correct 230 ms 259844 KB Output is correct
31 Correct 260 ms 262312 KB Output is correct
32 Correct 1544 ms 439552 KB Output is correct
33 Correct 1293 ms 436860 KB Output is correct
34 Correct 1577 ms 449908 KB Output is correct
35 Correct 1605 ms 445788 KB Output is correct
36 Correct 1346 ms 445352 KB Output is correct
37 Correct 1549 ms 450004 KB Output is correct
38 Correct 1807 ms 465484 KB Output is correct
39 Correct 1931 ms 465456 KB Output is correct
40 Correct 1728 ms 454024 KB Output is correct
41 Correct 2124 ms 477008 KB Output is correct
42 Correct 2338 ms 479456 KB Output is correct
43 Correct 2310 ms 479412 KB Output is correct
44 Correct 2441 ms 465080 KB Output is correct