Submission #1079947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079947		robloxuser4321	Pilot (NOI19_pilot)	C++17	100 / 100	705 ms	83320 KiB

pilot

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

#define int long long
#define pii pair<int, int>
#define f first
#define s second

vector<int> parents(1000006, -1);
vector<int> sizes(1000006);

class DisjointSets {

	public:
		DisjointSets(int size) {
			for (int i = 0; i < size; i++) { parents[i] = i; }
		}

		/** @return the "representative" node in x's component */
		int find(int x) {
			return parents[x] == x ? x : (parents[x] = find(parents[x]));
		}

		/** @return whether the merge changed connectivity */
		int unite(int x, int y) {
			int x_root = find(x);
			int y_root = find(y);
			if (x_root == y_root) { return 0; }

			if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
			
			int A = sizes[x_root], B = sizes[y_root];
			/*int ans = ((A + B) * (A + B - 1)) / 2;
			ans -= (A * (A - 1)) / 2;
			ans -= (B * (B - 1)) / 2;*/

			sizes[x_root] += sizes[y_root];
			parents[y_root] = x_root;
			return A * B;
		}

		/** @return whether x and y are in the same connected component */
		bool connected(int x, int y) { return find(x) == find(y); }
};

signed main() {
	int N, Q; cin >> N >> Q;

	vector<pii> H;
	vector<int> M(N + 6);

	for(int i = 1; i <= N; i++){
		cin >> M[i];
		H.push_back({M[i], -i});
	}
	M[N + 1] = 1000000006;
	M[0] = 1000000006;

	for(int i = 1; i <= Q; i++){
		int x; cin >> x;
		H.push_back({x, i});
	}

	sort(H.begin(), H.end());

	DisjointSets DSU(N + 6);

	vector<int> ans(Q + 1);
	int count = 0;
	for(int i = 0; i < N + Q; i++){
		int Alt = H[i].f, ind = H[i].s;

		if(ind > 0){
			ans[ind] = count;
			continue;
		}

		count++;
		ind *= -1;
		parents[ind] = ind;
		sizes[ind] = 1;

		if(Alt >= M[ind + 1]){
			count += DSU.unite(ind, ind + 1);
		}		
		if(Alt >= M[ind - 1]){
			count += DSU.unite(ind, ind - 1);
		}


	}

	for(int i = 1; i <= Q; i++){
		cout << ans[i] << " ";
	}




	




}

• 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: 11 / 11