Submission #1063011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063011		_rain_	Pilot (NOI19_pilot)	C++14	100 / 100	352 ms	53072 KiB

pilot

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define debug false

const int maxn = 1e6;
struct QUERY
{
	int q;
	int id;
	bool operator < (const QUERY& other) const{
		return q < other.q;
	}
};
QUERY p[maxn+2],a[maxn+2];
i64 answer = 0 , ans[maxn+2] = {};
int par[maxn+2] , sz[maxn+2];
int n , q;
bool used[maxn+2];

i64 get(int sz){
	return (i64)sz*(sz+1)/2;
}
int find(int u){
	return u == par[u] ? par[u] : par[u] = find(par[u]);
}
void unite(int u , int v){
	u = find(u) , v = find(v);
	if (u==v) return;
	if (sz[u] < sz[v]) swap(u,v);
	answer -= get(sz[v]); answer -= get(sz[u]);
	par[v] = u;
	sz[u] += sz[v];
	answer += get(sz[u]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) sz[i] = 1 , par[i] = i;
	for (int i = 1; i <= n; ++i){
		cin >> a[i].q;
		a[i].id = i;
	}
	for (int i = 1; i <= q; ++i){
		cin >> p[i].q;
		p[i].id = i;
	}
	sort(a+1,a+n+1);
	sort(p+1,p+q+1);
	int idx = 1;
	for (int i = 1; i <= q; ++i){
		while (idx <= n && a[idx].q <= p[i].q){
			int id = a[idx].id;
			answer += get(sz[id]);
			if (used[id - 1]) unite(id - 1 , id);
			if (used[id + 1]) unite(id , id + 1);
			used[id] = true;
			++idx;
		}
		ans[p[i].id] = answer;
	}
	for (int i = 1; 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