Submission #219738

#	Time	Username	Problem	Language	Result	Execution time	Memory
219738		atoiz	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	1047 ms	51704 KiB

constellation3

/*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 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65