oj.uz

Submission #368110

# Submission time Handle Problem Language Result Execution time Memory
368110 2021-02-19T14:23:53 Z Akashi Meetings (IOI18_meetings) C++14
100 / 100
 3044 ms 325136 KB 
#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

const int DIM = 750005;
const long long INF = 1e18;

int n;
int val[DIM];

struct Line {
	long long a, b;
	Line(long long _a = 0, long long _b = 0) {a = _a; b = _b;}
	long long get(int t) {
		return 1LL * a * t + b;
	}
};

struct SegTree {
	long long lazy[4 * DIM];
	Line line[4 * DIM];

	void build(int st = 1, int dr = n, int nod = 1) {
		lazy[nod] = 0; line[nod] = {0, INF};
		if (st == dr) {line[nod] = {0, 0}; return ;} 
		build(st, (st + dr) / 2, nod * 2);
		build((st + dr) / 2 + 1, dr, nod * 2 + 1);
	}

	void upd(int nod, long long val) {
		lazy[nod] += val;
		line[nod].b += val;
	}

	void propag(int nod) {
		if (lazy[nod] == 0) return ;
		for (int i = nod * 2; i <= nod * 2 + 1 ; ++i) upd(i, lazy[nod]);	
		lazy[nod] = 0;
	}

	long long query(int x, int st = 1, int dr = n, int nod = 1) {
		if (st == dr) return line[nod].get(x);
		propag(nod);
		int mij = (st + dr) / 2;
		if (x <= mij) return min(line[nod].get(x), query(x, st, mij, nod * 2));
		return min(line[nod].get(x), query(x, mij + 1, dr, nod * 2 + 1));
	}

	void update(int x, int y, long long val, int st = 1, int dr = n, int nod = 1) {
		if (x <= st && dr <= y) {upd(nod, val); return ;}
		propag(nod);
		int mij = (st + dr) / 2;
		if (x <= mij) update(x, y, val, st, mij, nod * 2);
		if (mij + 1 <= y) update(x, y, val, mij + 1, dr, nod * 2 + 1);
	}

	void idk(int l, int r, Line newLine, int st = 1, int dr = n, int nod = 1) {
		if (l <= st && dr <= r) {
			long long A = newLine.get(st), B = line[nod].get(st), C = newLine.get(dr), D = line[nod].get(dr);
			if (A <= B && C <= D) {line[nod] = newLine; return ;}
			if (A >= B && C >= D) return ;

			propag(nod);
			int mij = (st + dr) / 2;
			if (A <= B) swap(line[nod], newLine);

			if (line[nod].get(mij) <= newLine.get(mij)) idk(l, r, newLine, mij + 1, dr, nod * 2 + 1);
			else swap(line[nod], newLine), idk(l, r, newLine, st, mij, nod * 2);
			return ;
		}

		propag(nod);
		int mij = (st + dr) / 2;
		if (l <= mij) idk(l, r, newLine, st, mij, nod * 2);
		if (mij + 1 <= r) idk(l, r, newLine, mij + 1, dr, nod * 2 + 1);
	}

	void merge(int l, int split, int r, int tip) {
		if (tip == 0) {
			long long aux = query(split - 1);
			Line newLine = {val[split], aux - 1LL * (split - 1) * val[split]};
			idk(split, r, newLine);
		} else {
			long long aux = query(split + 1);
			Line newLine = {-val[split], aux + 1LL * (split + 1) * val[split]};
			idk(l, split, newLine); 
		}
	}
};

SegTree L, R;

struct query {
	int l, r, ind;
};

vector <long long> ans;
vector <query> myQ[DIM];

pair <int, int> arb[4 * DIM];
pair <int, int> max(pair <int, int> a, pair <int, int> b) {
	if (a.first > b.first || (a.first == b.first && a.second < b.second)) return a;
	return b;
}
void build_max(int st = 1, int dr = n, int nod = 1) {
	if (st == dr) {arb[nod] = {val[st], st}; return ;}
	int mij = (st + dr) / 2;
	build_max(st, mij, nod * 2);
	build_max(mij + 1, dr, nod * 2 + 1);
	arb[nod] = max(arb[nod * 2], arb[nod * 2 + 1]);
}

pair <int, int> _get_max(int x, int y, int st = 1, int dr = n, int nod = 1) {
	if (x <= st && dr <= y) return arb[nod];
	pair <int, int> ans = {-1, -1}; int mij = (st + dr) / 2;
	if (x <= mij) ans = max(ans, _get_max(x, y, st, mij, nod * 2));
	if (mij + 1 <= y) ans = max(ans, _get_max(x, y, mij + 1, dr, nod * 2 + 1));
	return ans;
}

int get_max(int x, int y) {
	return _get_max(x, y).second;
}

void solve(int l, int r) {
	if (l > r) return ;
	int split = get_max(l, r);

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

	for (auto it : myQ[split]) 
	ans[it.ind] = min(L.query(it.r) + 1LL * (split - it.l + 1) * val[split], R.query(it.l) + 1LL * (it.r - split + 1) * val[split]);
	
	L.update(split, r, 1LL * val[split] * (split - l + 1));
	if (split != l) L.merge(l, split, r, 0);

	R.update(l, split, 1LL * val[split] * (r - split + 1));
	if (split != r) R.merge(l, split, r, 1);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> LQ,
                                     std::vector<int> RQ) {
	n = (int)H.size();
	for (int i = 1; i <= n ; ++i) val[i] = H[i - 1];
	build_max();

	int Q = (int)LQ.size();
	ans.resize(Q);
	for (int i = 0; i < Q ; ++i) myQ[get_max(LQ[i] + 1, RQ[i] + 1)].push_back({LQ[i] + 1, RQ[i] + 1, i});

	L.build(); R.build();
	solve(1, n);
  return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 111852 KB Output is correct
2 Correct 70 ms 112108 KB Output is correct
3 Correct 69 ms 112108 KB Output is correct
4 Correct 68 ms 112108 KB Output is correct
5 Correct 67 ms 112108 KB Output is correct
6 Correct 77 ms 112364 KB Output is correct
7 Correct 68 ms 112108 KB Output is correct
8 Correct 73 ms 112364 KB Output is correct
9 Correct 69 ms 112236 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 111852 KB Output is correct
2 Correct 70 ms 112108 KB Output is correct
3 Correct 69 ms 112108 KB Output is correct
4 Correct 68 ms 112108 KB Output is correct
5 Correct 67 ms 112108 KB Output is correct
6 Correct 77 ms 112364 KB Output is correct
7 Correct 68 ms 112108 KB Output is correct
8 Correct 73 ms 112364 KB Output is correct
9 Correct 69 ms 112236 KB Output is correct
10 Correct 77 ms 112748 KB Output is correct
11 Correct 86 ms 112876 KB Output is correct
12 Correct 76 ms 112904 KB Output is correct
13 Correct 77 ms 112856 KB Output is correct
14 Correct 74 ms 113052 KB Output is correct
15 Correct 76 ms 112876 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111980 KB Output is correct
2 Correct 117 ms 115436 KB Output is correct
3 Correct 322 ms 130540 KB Output is correct
4 Correct 305 ms 124268 KB Output is correct
5 Correct 269 ms 131820 KB Output is correct
6 Correct 322 ms 132332 KB Output is correct
7 Correct 327 ms 133672 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111980 KB Output is correct
2 Correct 117 ms 115436 KB Output is correct
3 Correct 322 ms 130540 KB Output is correct
4 Correct 305 ms 124268 KB Output is correct
5 Correct 269 ms 131820 KB Output is correct
6 Correct 322 ms 132332 KB Output is correct
7 Correct 327 ms 133672 KB Output is correct
8 Correct 306 ms 124752 KB Output is correct
9 Correct 260 ms 124652 KB Output is correct
10 Correct 304 ms 124780 KB Output is correct
11 Correct 300 ms 124156 KB Output is correct
12 Correct 285 ms 123904 KB Output is correct
13 Correct 279 ms 124632 KB Output is correct
14 Correct 330 ms 130668 KB Output is correct
15 Correct 292 ms 123940 KB Output is correct
16 Correct 332 ms 130796 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 111852 KB Output is correct
2 Correct 70 ms 112108 KB Output is correct
3 Correct 69 ms 112108 KB Output is correct
4 Correct 68 ms 112108 KB Output is correct
5 Correct 67 ms 112108 KB Output is correct
6 Correct 77 ms 112364 KB Output is correct
7 Correct 68 ms 112108 KB Output is correct
8 Correct 73 ms 112364 KB Output is correct
9 Correct 69 ms 112236 KB Output is correct
10 Correct 77 ms 112748 KB Output is correct
11 Correct 86 ms 112876 KB Output is correct
12 Correct 76 ms 112904 KB Output is correct
13 Correct 77 ms 112856 KB Output is correct
14 Correct 74 ms 113052 KB Output is correct
15 Correct 76 ms 112876 KB Output is correct
16 Correct 71 ms 111980 KB Output is correct
17 Correct 117 ms 115436 KB Output is correct
18 Correct 322 ms 130540 KB Output is correct
19 Correct 305 ms 124268 KB Output is correct
20 Correct 269 ms 131820 KB Output is correct
21 Correct 322 ms 132332 KB Output is correct
22 Correct 327 ms 133672 KB Output is correct
23 Correct 306 ms 124752 KB Output is correct
24 Correct 260 ms 124652 KB Output is correct
25 Correct 304 ms 124780 KB Output is correct
26 Correct 300 ms 124156 KB Output is correct
27 Correct 285 ms 123904 KB Output is correct
28 Correct 279 ms 124632 KB Output is correct
29 Correct 330 ms 130668 KB Output is correct
30 Correct 292 ms 123940 KB Output is correct
31 Correct 332 ms 130796 KB Output is correct
32 Correct 2449 ms 225448 KB Output is correct
33 Correct 1772 ms 224248 KB Output is correct
34 Correct 2061 ms 228428 KB Output is correct
35 Correct 2454 ms 228160 KB Output is correct
36 Correct 1783 ms 226060 KB Output is correct
37 Correct 2065 ms 229024 KB Output is correct
38 Correct 2597 ms 277492 KB Output is correct
39 Correct 2637 ms 277576 KB Output is correct
40 Correct 2542 ms 235588 KB Output is correct
41 Correct 2608 ms 322448 KB Output is correct
42 Correct 3003 ms 325136 KB Output is correct
43 Correct 3044 ms 324904 KB Output is correct
44 Correct 2974 ms 277024 KB Output is correct