Submission #225302

#	Time	Username	Problem	Language	Result	Execution time	Memory
225302		vioalbert	Pilot (NOI19_pilot)	C++14	100 / 100	692 ms	67872 KiB

pilot

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

const int N = 1000005;
int n, q;
int h[N], y[N];

struct event {
	int ty, h, idx;
	bool operator<(const event& ot) {
		if(h == ot.h)
			return ty < ot.ty;
		return h < ot.h;
	}
};

ll cur;
ll ans[N];
vector<event> events;
int par[N], sz[N];

int find(int x) {
	if(par[x] == -1) return -1;
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
}

void join(int x, int y) {
	int parX = find(x);
	int parY = find(y);
	par[parX] = parY;
	sz[parY] = sz[parX] + sz[parY];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		cin >> h[i];
		events.push_back({0, h[i], i});
	}
	for(int i = 0; i < q; i++) {
		cin >> y[i];
		events.push_back({1, y[i], i});
	}

	for(int i = 0; i < n; i++) {
		par[i] = -1;
		sz[i] = 1;
	}

	sort(events.begin(), events.end());
	cur = 0;
	for(auto& e : events) {
		if(e.ty == 0) {
			par[e.idx] = e.idx;

			ll l = 0, r = 0;

			if(e.idx > 0 && par[e.idx-1] != -1) {
				l = sz[find(e.idx-1)];
				join(e.idx, e.idx-1);
			}

			if(e.idx < n-1 && par[e.idx+1] != -1) {
				r = sz[find(e.idx+1)];
				join(e.idx, e.idx+1);
			}

			cur += (l+1) * (r+1);
		} else {
			ans[e.idx] = cur;
		}
	}

	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';

	return 0;
}

• 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