oj.uz

Submission #219738

# Submission time Handle Problem Language Result Execution time Memory
219738 2020-04-06T08:09:36 Z atoiz Constellation 3 (JOI20_constellation3) C++14
100 / 100
 1047 ms 51704 KB 
/*input
8
6 8 5 7 3 4 2 1
10
8 2 9
6 6 7
8 3 18
5 8 17
8 5 3
5 5 3
5 4 8
1 8 13
1 7 5
7 4 13
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <tuple>
#include <map>
#include <numeric>

using namespace std;

void maximize(int64_t &x, int64_t y)
{ x = (x > y ? x : y); }

struct FenwickTree
{
	int N;
	vector<int64_t> A;

	FenwickTree(int _N): N(_N + 3), A(N, 0) {};

	void add(int l, int r, int64_t x)
	{
		l += 1, r += 2;
		for (; l <= N; l += l & (-l)) A[l] += x;
		for (; r <= N; r += r & (-r)) A[r] -= x;
	}

	int64_t get(int id)
	{
		int64_t val = 0;
		for (id += 1; id > 0; id -= id & (-id)) val += A[id];
		return val;
	}
};

using point_t = tuple<int, int, int>;

const int MAXN = 200006, LOG = __lg(MAXN) + 1;
int N, M, A[MAXN];
int nxt_lef[MAXN], nxt_rig[MAXN];
int jump_lef[LOG][MAXN], jump_rig[LOG][MAXN];
int64_t total_C = 0;
map<pair<int, int>, vector<point_t>> points;
vector<int> ids;

#define less less_
bool less(int i, int j)
{ return make_pair(A[i], i) < make_pair(A[j], j); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	A[0] = A[N + 1] = MAXN;

	nxt_lef[0] = 0, nxt_rig[N + 1] = N + 1;
	for (int i = 1; i <= N; ++i) {
		for (nxt_lef[i] = i - 1; less(nxt_lef[i], i); nxt_lef[i] = nxt_lef[nxt_lef[i]]); 
	}
	for (int i = N; i >= 1; --i) {
		for (nxt_rig[i] = i + 1; less(nxt_rig[i], i); nxt_rig[i] = nxt_rig[nxt_rig[i]]); 
	}
	jump_lef[0][0] = 0, jump_rig[0][N + 1] = N + 1;
	for (int i = 1; i <= N; ++i) jump_lef[0][i] = nxt_lef[i], jump_rig[0][i] = nxt_rig[i];
	for (int j = 1; j < LOG; ++j) for (int i = 0; i <= N + 1; ++i) {
		jump_lef[j][i] = jump_lef[j - 1][jump_lef[j - 1][i]];
		jump_rig[j][i] = jump_rig[j - 1][jump_rig[j - 1][i]];
	}

	cin >> M;
	while (M--) {
		int x, y, c;
		cin >> x >> y >> c;

		int l = x, r = x;
		for (int j = LOG - 1; j >= 0; --j) {
			if (A[jump_lef[j][l]] < y) l = jump_lef[j][l]; 
			if (A[jump_rig[j][r]] < y) r = jump_rig[j][r]; 
		}
		l = nxt_lef[l], r = nxt_rig[r];
		points[make_pair(l, r)].emplace_back(x, y, c);

		total_C += c;
	}

	FenwickTree bit_l(N + 2), bit_r(N + 2);

	ids.resize(N);
	iota(ids.begin(), ids.end(), 1);
	sort(ids.begin(), ids.end(), less);
	for (int mid : ids) {
		int lef = nxt_lef[mid], rig = nxt_rig[mid];
		int64_t val_lef = bit_r.get(lef), val_rig = bit_l.get(rig);
		int64_t cur = val_lef + val_rig, val = cur;

		bit_r.add(lef, mid - 1, val_rig);
		bit_l.add(mid + 1, rig, val_lef);

		if (points.find(make_pair(lef, rig)) != points.end()) {
			for (auto point : points[make_pair(lef, rig)]) {
				int x, y, c;
				tie(x, y, c) = point;
				assert(y > A[mid] && y <= A[lef] && y <= A[rig]);
				assert(lef < x && x < rig);

				maximize(val, c + bit_l.get(x) + bit_r.get(x));
			}
		}

		bit_r.add(lef, lef, val - cur);
		bit_l.add(rig, rig, val - cur);
	}

	cout << total_C - bit_r.get(0) << endl;
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 5 ms 640 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 5 ms 640 KB Output is correct
19 Correct 6 ms 768 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 5 ms 640 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 5 ms 640 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 5 ms 640 KB Output is correct
19 Correct 6 ms 768 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 5 ms 640 KB Output is correct
23 Correct 7 ms 1024 KB Output is correct
24 Correct 8 ms 896 KB Output is correct
25 Correct 8 ms 1024 KB Output is correct
26 Correct 7 ms 1024 KB Output is correct
27 Correct 7 ms 1024 KB Output is correct
28 Correct 7 ms 1024 KB Output is correct
29 Correct 8 ms 1024 KB Output is correct
30 Correct 7 ms 1024 KB Output is correct
31 Correct 8 ms 1152 KB Output is correct
32 Correct 7 ms 1024 KB Output is correct
33 Correct 8 ms 1024 KB Output is correct
34 Correct 8 ms 1024 KB Output is correct
35 Correct 7 ms 1024 KB Output is correct
36 Correct 7 ms 1024 KB Output is correct
37 Correct 7 ms 1044 KB Output is correct
38 Correct 7 ms 1024 KB Output is correct
39 Correct 7 ms 1024 KB Output is correct
40 Correct 7 ms 1024 KB Output is correct
41 Correct 7 ms 1024 KB Output is correct
42 Correct 7 ms 1024 KB Output is correct
43 Correct 7 ms 1024 KB Output is correct
44 Correct 7 ms 1024 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 5 ms 640 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 5 ms 640 KB Output is correct
19 Correct 6 ms 768 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 5 ms 640 KB Output is correct
23 Correct 7 ms 1024 KB Output is correct
24 Correct 8 ms 896 KB Output is correct
25 Correct 8 ms 1024 KB Output is correct
26 Correct 7 ms 1024 KB Output is correct
27 Correct 7 ms 1024 KB Output is correct
28 Correct 7 ms 1024 KB Output is correct
29 Correct 8 ms 1024 KB Output is correct
30 Correct 7 ms 1024 KB Output is correct
31 Correct 8 ms 1152 KB Output is correct
32 Correct 7 ms 1024 KB Output is correct
33 Correct 8 ms 1024 KB Output is correct
34 Correct 8 ms 1024 KB Output is correct
35 Correct 7 ms 1024 KB Output is correct
36 Correct 7 ms 1024 KB Output is correct
37 Correct 7 ms 1044 KB Output is correct
38 Correct 7 ms 1024 KB Output is correct
39 Correct 7 ms 1024 KB Output is correct
40 Correct 7 ms 1024 KB Output is correct
41 Correct 7 ms 1024 KB Output is correct
42 Correct 7 ms 1024 KB Output is correct
43 Correct 7 ms 1024 KB Output is correct
44 Correct 7 ms 1024 KB Output is correct
45 Correct 1047 ms 51704 KB Output is correct
46 Correct 991 ms 51012 KB Output is correct
47 Correct 1037 ms 50744 KB Output is correct
48 Correct 1012 ms 51360 KB Output is correct
49 Correct 993 ms 50168 KB Output is correct
50 Correct 1010 ms 50040 KB Output is correct
51 Correct 998 ms 50300 KB Output is correct
52 Correct 1024 ms 51448 KB Output is correct
53 Correct 1000 ms 51064 KB Output is correct
54 Correct 840 ms 50296 KB Output is correct
55 Correct 820 ms 48248 KB Output is correct
56 Correct 790 ms 47096 KB Output is correct
57 Correct 783 ms 46328 KB Output is correct
58 Correct 562 ms 42360 KB Output is correct
59 Correct 570 ms 42360 KB Output is correct
60 Correct 320 ms 50296 KB Output is correct
61 Correct 751 ms 46072 KB Output is correct
62 Correct 810 ms 49144 KB Output is correct
63 Correct 728 ms 45492 KB Output is correct
64 Correct 713 ms 44792 KB Output is correct
65 Correct 832 ms 49400 KB Output is correct
66 Correct 722 ms 44664 KB Output is correct