Submission #629678

#	Time	Username	Problem	Language	Result	Execution time	Memory
629678		flappybird	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	4502 ms	243496 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]) 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);
	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];
	}
	memset(p, 0, sizeof(p));
	for (i = 1; i <= M; i++) {
		for (j = i; j >= 1; j--) if (!uni(j, A[i], B[i])) break;
		l[i] = W[j];
	}
	vector<pll> sum, mul;
	for (i = 1; i <= M; i++) {
		if (l[i] != W[i]) {
			ll loc = (W[i] + l[i]) / 2 + 1;
			sum.emplace_back(loc, W[i]);
			sum.emplace_back(W[i], -W[i]);
			mul.emplace_back(loc, -1);
			mul.emplace_back(W[i], 1);
		}
		if (r[i] != W[i]) {
			ll loc = (W[i] + r[i]) / 2;
			sum.emplace_back(W[i] + 1, -W[i]);
			sum.emplace_back(loc + 1, W[i]);
			mul.emplace_back(W[i] + 1, 1);
			mul.emplace_back(loc + 1, -1);
		}
	}
	sort(mul.begin(), mul.end());
	sort(sum.begin(), sum.end());
	int Q;
	cin >> Q;
	ll s, m;
	s = m = 0;
	int ptr1, ptr2;
	ptr1 = 0, ptr2 = 0;
	while (Q--) {
		ll x;
		cin >> x;
		while (ptr1 < sum.size() && sum[ptr1].first <= x) s += sum[ptr1++].second;
		while (ptr2 < mul.size() && mul[ptr2].first <= x) m += mul[ptr2++].second;
		cout << x * m + s << ln;
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   while (ptr1 < sum.size() && sum[ptr1].first <= x) s += sum[ptr1++].second;
      |          ~~~~~^~~~~~~~~~~~
reconstruction.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   while (ptr2 < mul.size() && mul[ptr2].first <= x) m += mul[ptr2++].second;
      |          ~~~~~^~~~~~~~~~~~

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