제출 #332997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332997		guka415	Pilot (NOI19_pilot)	C++14	100 / 100	705 ms	63980 KiB

pilot

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;




const int sz = 1e6 + 5;

struct dsu {
	int f[sz], p[sz], rk[sz];
	dsu(int n) {
		foru(i, 0, n) { f[i] = i; p[i] = 1; rk[i] = 1; }
	}
	int father(int src) {
		if (f[src] != src)return f[src] = father(f[src]);
		else return src;
	}
	bool unite(int a, int b) {
		int fa = father(a), fb = father(b);
		if (fa == fb)return 0;
		if (rk[fa] < rk[fb])swap(fa, fb);
		rk[fa] = max(rk[fa], rk[fb] + 1);
		f[fb] = fa;
		p[fa] += p[fb];
		return 1;
	}
};

int n, q;
ll h[sz];
pii g[sz];
pii qu[sz];
ll ans[sz];
bitset<sz> on;

void input() {
	cin >> n >> q;
	foru(i, 0, n) {
		cin >> h[i]; g[i].first = h[i];
		g[i].second = i;
	}
	foru(i, 0, q) {
		cin >> qu[i].first;
		qu[i].second = i;
	}
	sort(qu, qu + q);
	sort(g, g + n);
}


ll calc(ll x) {
	return (x * (x + 1)) / 2;
}

int main() {
	fast;
	input();
	dsu d(n);
	ll ret = 0;
	int ind = 0;
	foru(i, 0, q) {
		while (ind < n && h[g[ind].second] <= qu[i].first) {
			int px = g[ind].second;
			on[px] = 1;
			if (px && on[px - 1]) {
				ret -= calc(d.p[d.father(px - 1)]);
				d.unite(px, px - 1);
			}
			if (px != n - 1 && on[px + 1]) {
				ret -= calc(d.p[d.father(px + 1)]);
				d.unite(px, px + 1);
			}
			ret += calc(d.p[d.father(px)]);
			ind++;
		}
		ans[qu[i].second] = ret;
	}
	foru(i, 0, q)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