Submission #321153

#	Time	Username	Problem	Language	Result	Execution time	Memory
321153		socho	Pilot (NOI19_pilot)	C++14	100 / 100	700 ms	76584 KiB

pilot

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

long long ans = 0;

const long long MXN = 1000005;
long long par[MXN], gs[MXN];
bool used[MXN];

void init() {
	for (long long i=0; i<MXN; i++) par[i] = i;
}

long long parent(long long n) {
	if (n == par[n]) return n;
	return par[n] = parent(par[n]);
}

bool arc(long long a, long long b) {
	return parent(a) == parent(b);
}

long long pa(long long n) {
	return n * (n+1) / 2;
}

void connect(long long a, long long b) {
	if (arc(a, b)) return;
	long long ax = parent(a);
	long long bx = parent(b);
	long long oa = gs[ax];
	long long ob = gs[bx];
	ans -= pa(oa);
	ans -= pa(ob);
	ans += pa(oa+ob);
	gs[ax] += gs[bx];
	par[bx] = ax;
}

void prop(long long n) {
	if (used[n-1] && used[n]) {
		connect(n-1, n);
	}
	if (used[n] && used[n+1]) {
		connect(n, n+1);
	}
}


int main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    long long n, q;
    cin >> n >> q;
    vector<pair<long long, long long> > ar(n);
    for (long long i=0; i<n; i++) {
		long long x;
		cin >> x;
		ar[i] = make_pair(x, i+1);
	}
	vector<pair<long long, long long> > qs;
	for (long long i=0; i<q; i++) {
		long long x;
		cin >> x;
		qs.push_back(make_pair(x, i));
	}
	
	memset(used, 0, sizeof used);
	
	sort(ar.begin(), ar.end());
	sort(qs.begin(), qs.end());
	
	long long nxt = 0;
	
	long long res[q];
	
	init();
	
	for (long long i=0; i<q; i++) {
		long long qx = qs[i].first;
		long long pos = qs[i].second;
		while (nxt < n && ar[nxt].first <= qx) {
			ans++;
			used[ar[nxt].second] = true;
			gs[ar[nxt].second] = 1;
			prop(ar[nxt].second);
			nxt++;
		}
		res[pos] = ans;
	}
	
	for (long long i=0; i<q; i++) cout << res[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