Submission #780365

#	Time	Username	Problem	Language	Result	Execution time	Memory
780365		ymm	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	296 ms	42048 KiB

constellation3

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
#define LoopR(x, l, r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;


struct node {
	int l, r;
	int pos;
	ll C;
	vector<node *> adj;
	ll dp;
	int st, ft;
};

vector<node> nds;

const int N = 200'010;
pii a[N];
struct star {
	int x, y;
	ll C;
} stars[N];
int n, m;

namespace segmx {
	int a[2*N];

	void up(int l, int r, int x) {
		l += N;
		r += N;
		while (l < r) {
			if (l&1) { a[l] = max(a[l], x); ++l; }
			if (r&1) { --r; a[r] = max(a[r], x); }
			l /= 2;
			r /= 2;
		}
	}
	int get(int p) {
		int ans = 0;
		p += N;
		while (p) {
			ans = max(ans, a[p]);
			p /= 2;
		}
		return ans;
	}
}
namespace segadd {
	ll a[2*N];

	void up(int l, int r, ll x) {
		l += N;
		r += N;
		while (l < r) {
			if (l&1) { a[l] = a[l]+x; ++l; }
			if (r&1) { --r; a[r] = a[r]+x; }
			l /= 2;
			r /= 2;
		}
	}
	ll get(int p) {
		ll ans = 0;
		p += N;
		while (p) {
			ans += a[p];
			p /= 2;
		}
		return ans;
	}
}

void mk_nodes()
{
	sort(stars, stars+m, [](star &a, star &b) {
		return a.y < b.y;
	});
	sort(a, a+n);
	set<int> cur_buildings = {-1, n};
	int p = n-1;
	LoopR (i,0,m) {
		while (p >= 0 && a[p].first > stars[i].y)
			cur_buildings.insert(a[p--].second);
		int l = *--cur_buildings.lower_bound(stars[i].x)+1;
		int r = *cur_buildings.upper_bound(stars[i].x);
		node dard = {
			.l = l,
			.r = r,
			.pos = stars[i].x,
			.C = stars[i].C,
			.adj = {},
			.dp = 0,
			.st = 0,
			.ft = 0,
		};
		nds.push_back(dard);
	}
	sort(nds.begin(), nds.end(), [](node &a, node &b) {
		return a.l < b.l || (a.l == b.l && a.r > b.r);
	});
}

void process(node *t)
{
	node *c = NULL;
	t->dp = 0;
	for (auto u : t->adj) {
		t->dp += u->dp;
		if (t->pos < u->l || u->r <= t->pos)
			continue;
		assert(c == NULL);
		c = u;
	}
	ll x = t->dp + t->C;
	if (c) {
		x -= c->dp;
		int pos = segmx::get(t->pos);
		//cout << t->l << ' ' << t->pos << ' ' << t->r << " vv " << pos << '\n';
		x += segadd::get(nds[pos].st);
	}
	for (auto u : t->adj)
		segadd::up(u->st, u->ft, t->dp - u->dp);
	segadd::up(t->st, t->st+1, t->dp);
	t->dp = max(t->dp, x);
}

void dfs_stft(node *t, int &pos)
{
	t->st = pos++;
	for (node *u : t->adj)
		dfs_stft(u, pos);
	t->ft = pos;
}

void dfs_dp(node *t)
{
	for (node *u : t->adj)
		dfs_dp(u);
	process(t);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		cin >> a[i].first;
		a[i].second = i;
	}
	cin >> m;
	ll sumC = 0;
	Loop (i,0,m) {
		cin >> stars[i].x >> stars[i].y >> stars[i].C;
		sumC += stars[i].C;
		--stars[i].x; --stars[i].y;
		//cout << stars[i].x << ' ' << stars[i].y << '\n';
	}
	mk_nodes();
	vector<node *> vec;
	vector<node *> rts;
	Loop (i,0,nds.size()) {
		node *t = &nds[i];
		while (vec.size() && vec.back()->r <= t->l)
			vec.pop_back();
		if (vec.size())
			vec.back()->adj.push_back(t);
		else
			rts.push_back(t);
		vec.push_back(t);
		segmx::up(t->l, t->r, i);
	}
	int dard = 0;
	for (auto t : rts)
		dfs_stft(t, dard);
	ll ans = 0;
	for (auto t : rts) {
		dfs_dp(t);
		ans += t->dp;
	}
	Loop (i,0,nds.size()) {
		//cout << nds[i].l << ' ' << nds[i].pos << ' ' << nds[i].r << " -> " << nds[i].dp << '\n';
	}
	cout << sumC - ans << '\n';
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:2:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
      |                                          ^
constellation3.cpp:163:2: note: in expansion of macro 'Loop'
  163 |  Loop (i,0,nds.size()) {
      |  ^~~~
constellation3.cpp:2:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
      |                                          ^
constellation3.cpp:182:2: note: in expansion of macro 'Loop'
  182 |  Loop (i,0,nds.size()) {
      |  ^~~~

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