제출 #252028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252028		Bruteforceman	별자리 3 (JOI20_constellation3)	C++11	100 / 100	514 ms	58872 KiB

constellation3

#include "bits/stdc++.h"
using namespace std;
using pii = pair <int, int>;
int a[200010];
map <pii, vector <pii>> cont;
vector <int> g[200010];
vector <pii> star[200010];
vector <int> v[200010];
vector <pii> node;

int disc[200010], fin[200010];
int leaf[200010];
long long dp[200010];

int cur;
void dfs(int x) {
	disc[x] = ++cur;
	for(auto i : g[x]) {
		dfs(i);
	}
	fin[x] = cur;
}
long long t[200010];
void update(int x, long long val) {
	for(int i = x; i <= cur; i += i & (-i)) {
		t[i] += val;
	}
}
long long query(int x) {
	long long ans = 0;
	for(int i = x; i > 0; i -= i & (-i)) {
		ans += t[i]; 
	}
	return ans;
}

void solve(int i) {
	dp[i] = 0;
	for(auto j : g[i]) {
		solve(j);
		dp[i] += dp[j];
	}
	for(auto j : g[i]) {
		update(disc[i], dp[j]); update(fin[i] + 1, -dp[j]);
		update(disc[j], -dp[j]); update(fin[j] + 1, dp[j]);
	}
	for(auto j : star[i]) {
		int pos = disc[leaf[j.first]];
		dp[i] = max(dp[i], query(pos) + j.second);
	}
}

int prop[200010 * 4];
void assign(int x, int y, int val, int c, int b, int e) {
	if(x <= b && e <= y) {
		prop[c] = min(prop[c], val);
		return ;
	}
	if(y < b || e < x) return ;
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	assign(x, y, val, l, b, m);
	assign(x, y, val, r, m + 1, e);
}
int get(int x, int c, int b, int e) {
	if(b == e) return prop[c];
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) return min(prop[c], get(x, l, b, m));
	else return min(prop[c], get(x, r, m + 1, e)); 
}

int x[200010], y[200010], c[200010];
int l[200010], r[200010];
vector <pii> mono;
int search(int l, int r, int val) {
	if(l == r) {
		return mono[l].second;
	}
	int m = (l + r + 1) >> 1;
	if(mono[m].first >= val) return search(m, r, val);
	else return search(l, m - 1, val);
}
int main(int argc, char const *argv[])
{
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	int m;
	scanf("%d", &m);
	long long total = 0;
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d", &x[i], &y[i], &c[i]);
		total += c[i];
		v[x[i]].emplace_back(i);
	}
	mono.emplace_back(INT_MAX, 0);
	for(int i = 1; i <= n; i++) {
		while(mono.back().first <= a[i]) {
			mono.pop_back();
		}
		mono.emplace_back(a[i], i);
		for(auto j : v[i]) {
			l[j] = search(0, mono.size() - 1, y[j]) + 1;
		}
	}
	mono.resize(1);
	mono[0].second = n + 1;
	for(int i = n; i >= 1; i--) {
		while(mono.back().first <= a[i]) {
			mono.pop_back();
		}
		mono.emplace_back(a[i], i);
		for(auto j : v[i]) {
			r[j] = search(0, mono.size() - 1, y[j]) - 1;
		}
	}
	for(int i = 1; i <= m; i++) {
		cont[pii(l[i], r[i])].push_back(pii(x[i], c[i]));
	}
	for(auto i : cont) {
		node.push_back(i.first);
	}
	sort(node.begin(), node.end(), [] (pii p, pii q) { return (p.second - p.first) < (q.second - q.first); });
	set <pii> active; 
	memset(leaf, -1, sizeof leaf);
	memset(prop, 63, sizeof prop);
	for(int id = 0; id < node.size(); id++) {
		while(true) {
			auto it = active.lower_bound(pii(node[id].first, -1));
			if(it != active.end() && it -> first <= node[id].second) {
				g[id].push_back(it -> second);
				active.erase(it);
			} else break;
		}
		active.insert(pii(node[id].first, id));
		star[id] = cont[node[id]];
		assign(node[id].first, node[id].second, id, 1, 1, n);
	} 
	int root = node.size();
	node.emplace_back(1, n);
	for(auto i : active) {
		g[root].push_back(i.second);
	}
	assign(1, n, root, 1, 1, n);
	for(int i = 1; i <= n; i++) {
		leaf[i] = get(i, 1, 1, n);
	}
	dfs(root);
	solve(root);
	printf("%lld\n", total - dp[root]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'int main(int, const char**)':
constellation3.cpp:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int id = 0; id < node.size(); id++) {
                  ~~~^~~~~~~~~~~~~
constellation3.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
constellation3.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
constellation3.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
constellation3.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x[i], &y[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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