Submission #471283

#	Time	Username	Problem	Language	Result	Execution time	Memory
471283		prvocislo	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	380 ms	29112 KiB

constellation3

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

const int maxn = 1 << 18;
ll tree[maxn * 2];
void range_add(int l, int r, ll d)
{
	for (l += maxn, r += maxn+1; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1) tree[l++] += d;
		if (r & 1) tree[--r] += d;
	}
}
ll query(int i)
{
	ll ans = 0;
	for (i += maxn; i > 0; i >>= 1) ans += tree[i];
	return ans;
}
struct star { int x, y, c; };
bool cmp(const star& a, const star& b) { return (a.y < b.y || (a.y == b.y && a.x < b.x)); }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n + 2, n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	int m;
	cin >> m;
	vector<int> l(m, -1), r(m, -1);
	ll ans = 0;
	vector<star> s(m);
	for (int i = 0; i < m; i++) cin >> s[i].x >> s[i].y >> s[i].c, ans += s[i].c;
	sort(s.begin(), s.end(), cmp);
	vector<vector<int> > v(n + 2);
	for (int i = 0; i < m; i++) v[s[i].x].push_back(i);
	vector<int> stk = {0};
	set<pair<int, int> > tall = { { a[0], 0 } };
	for (int i = 1; i <= n; i++)
	{
		while (!stk.empty() && a[stk.back()] <= a[i]) tall.erase({ a[stk.back()], stk.back() }), stk.pop_back();
		for (int j : v[i])
			l[j] = tall.upper_bound({ s[j].y, -1 })->second;
		tall.insert({ a[i], i });
		stk.push_back(i);
	}
	stk = { n + 1 }, tall = { { a[n + 1], n + 1 } };
	for (int i = n; i >= 1; i--)
	{
		while (!stk.empty() && a[stk.back()] <= a[i]) tall.erase({ a[stk.back()], stk.back() }), stk.pop_back();
		for (int j : v[i]) 
			r[j] = tall.upper_bound({ s[j].y, -1 })->second;
		tall.insert({ a[i], i });
		stk.push_back(i);
	}
	for (int i = 0; i < m; i++)
	{
		ll val = (ll)s[i].c - query(s[i].x);
		if (val > 0)
		{
			range_add(l[i] + 1, r[i] - 1, val);
			ans -= val;
		}
		/*for (int j = 0; j < n; j++) cout << query(j) << " ";
		cout << "\n";*/
	}
	cout << ans << "\n";
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65