제출 #538925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538925		_karan_gandhi	Pilot (NOI19_pilot)	C++17	89 / 100	1056 ms	56880 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

ll int cnt = 0;

struct DSU {
	vector<int> p, s;

	void init(int n) {
		p = vector<int>(n);
		s = vector<int>(n, 1);
		iota(all(p), 0);
	}

	int get(int x) {
		return p[x] = (p[x] == x ? x : get(p[x]));
	}

	void unite(int a, int b) {
		if (a == b) {
			cnt++;
			return;
		}
		a = get(a);
		b = get(b);


		if (a == b) {
			return;
		}

		if (s[a] > s[b]) swap(a, b);
		p[a] = b;
		cnt += ((ll int)s[b]) * ((ll int)s[a]);
		s[b] += s[a];
	}
};

void solve() {
	int n; cin >> n;
	int q; cin >> q;

	vector<int> arr(n); for (int i = 0; i < n; i++) cin >> arr[i];
	vector<pair<int, pair<int, int>>> edges;

	for (int i = 1; i < n; i++) {
		edges.emplace_back(max(arr[i], arr[i - 1]), make_pair(i, i - 1));
	}

	for (int i = 0; i < n; i++) {
		edges.emplace_back(arr[i], make_pair(i, i));
	}


	sort(all(edges));

	vector<pair<int, int>> qq;
	for (int i = 0; i < q; i++) {
		int a; cin >> a;
		qq.emplace_back(a, i);
	}
	// cout << "Hello" << endl;

	sort(all(qq));

	vector<ll int> ans(q);
	int ptr = 0;

	DSU dsu;
	dsu.init(n);

	for (int i = 0; i < q; i++) {
		int hi = qq[i].first;
		// cout << pl(hi) << endl;
		
		while (ptr < int(edges.size()) && edges[ptr].first <= hi) {
			dsu.unite(edges[ptr].second.first, edges[ptr].second.second);
			// cout << pl(edges[ptr].first) << pl(edges[ptr].second.first) << pl(edges[ptr].second.second) << pl(cnt) << endl;
			ptr++;
		}

		ans[qq[i].second] = cnt;
	}

	for (ll int a : ans) {
		cout << a << endl;
	}
}

int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T--)
		solve();
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11