Submission #629673

#	Time	Username	Problem	Language	Result	Execution time	Memory
629673		flappybird	Reconstruction Project (JOI22_reconstruction)	C++17	38 / 100	5089 ms	264848 KiB

reconstruction

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 101010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int p[MAX][505];
ll r[MAX];
ll l[MAX];
int A[MAX];
int B[MAX];
ll W[MAX];
int find(int t, int x) {
	if (p[t][x] == x) return x;
	else return p[t][x] = find(t, p[t][x]);
}
bool uni(int t, int u, int v) {
	u = find(t, u);
	v = find(t, v);
	if (u == v) return false;
	p[t][u] = v;
	return true;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M;
	cin >> N >> M;
	int i, j;
	vector<pair<ll, pii>> in;
	int a, b, c;
	in.push_back({ 0, {0, 0} });
	for (i = 1; i <= M; i++) cin >> a >> b >> c, in.push_back(make_pair(c, pii(a, b)));
	sort(in.begin(), in.end());
	for (i = 1; i <= M; i++) tie(A[i], B[i], W[i]) = make_tuple(in[i].second.first, in[i].second.second, in[i].first);
	for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) p[j][i] = i;
	W[0] = -2000000010;
	W[M + 1] = 2000000010;
	for (i = M; i >= 1; i--) {
		for (j = i; j <= M; j++) if (!uni(j, A[i], B[i])) break;
		r[i] = W[j];
	}
	for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) p[j][i] = i;
	for (i = 1; i <= M; i++) {
		for (j = i; j >= 1; j--) if (!uni(j, A[i], B[i])) break;
		l[i] = W[j];
	}
	map<ll, ll> sum, mul;
	for (i = 1; i <= M; i++) {
		if (l[i] != W[i]) {
			ll loc = (W[i] + l[i]) / 2 + 1;
			sum[loc] += W[i];
			sum[W[i]] -= W[i];
			mul[loc]--;
			mul[W[i]]++;
		}
		if (r[i] != W[i]) {
			ll loc = (W[i] + r[i]) / 2;
			sum[W[i] + 1] -= W[i];
			sum[loc + 1] += W[i];
			mul[W[i] + 1]++;
			mul[loc + 1]--;
		}
	}
	sum[-1000000000000ll] = 0;
	mul[-1000000000000ll] = 0;
	ll pv = 0;
	for (auto& [x, y] : sum) y += pv, pv = y;
	pv = 0;
	for (auto& [x, y] : mul) y += pv, pv = y;
	int Q;
	cin >> Q;
	while (Q--) {
		ll x;
		cin >> x;
		ll s = prev(sum.upper_bound(x))->second;
		ll m = prev(mul.upper_bound(x))->second;
		cout << x * m + s << ln;
	}
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23