Submission #674739

#	Time	Username	Problem	Language	Result	Execution time	Memory
674739		QwertyPi	Pilot (NOI19_pilot)	C++14	100 / 100	551 ms	83224 KiB

pilot

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

const int MAXN = 1e6 + 11;

using namespace std;

int rans = 0;
struct DSU{
	int dsu[MAXN], sz[MAXN];
	void __init(int n){
		for(int i = 0; i <= n; i++){
			dsu[i] = i, sz[i] = 1;
		}
	}
	int f(int x){
		return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
	}
	int s(int x){
		return sz[f(x)];
	}
	void g(int x, int y){
		x = f(x), y = f(y);
		if(x != y){
			rans += sz[x] * sz[y];
			dsu[x] = y; sz[y] += sz[x];
		}
	}
} dsu;

int h[MAXN], ans[MAXN];

int32_t main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int n, q; cin >> n >> q;
	for(int i = 0; i < n; i++){
		cin >> h[i];
	}
	dsu.__init(n);
	vector<pair<int, int>> Q, pos;
	for(int i = 0; i < q; i++){
		int y; cin >> y; Q.push_back({y, i});
	}
	sort(Q.begin(), Q.end());
	for(int i = 0; i < n; i++){
		pos.push_back({h[i], i});
	}
	sort(pos.begin(), pos.end()); int pid = 0;
	for(auto i : Q){
		while(pid < n && pos[pid].fi <= i.fi) dsu.g(pos[pid].se, pos[pid].se + 1), pid++;
		ans[i.se] = rans;
	}
	for(int i = 0; i < q; i++){
		cout << ans[i] << '\n';
	}
}

• 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