Submission #572406

#	Time	Username	Problem	Language	Result	Execution time	Memory
572406		MODDI	Pilot (NOI19_pilot)	C++14	89 / 100	1085 ms	70940 KiB

pilot

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn = 1e6 + 5;
ll parent[maxn];
ll sz[maxn];
bool on[maxn];
ll find(int x) {return x == parent[x]?x:parent[x] = find(parent[x]);}
ll rez = 0;
void mrg(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    rez -= sz[a] * (sz[a]+1) / 2;
    rez -= sz[b] * (sz[b]+1) / 2;
    sz[a] += sz[b];
    rez += sz[a] * (sz[a]+1) / 2;
    parent[b] = a;
}
vector<ll> G[maxn];
ll ans[maxn];
signed main(){
 	ios::sync_with_stdio(0), cin.tie(0);
	int n, q;
	cin>>n>>q;
	for(int i = 0; i < n; i++){
		parent[i] = i;
		sz[i] = 1;
		int a;
		cin>>a;
		G[a].pb(i);
	}
	for(int i = 1; i <= 1000000; i++){
		for(int x : G[i]){
			++rez;
			on[x] = 1;
			if(x && on[x-1]) mrg(x, x-1);
			if(x != n-1 && on[x+1]) mrg(x, x + 1);
		}
		ans[i] = rez;
	}
	for(int i = 0; i < q; i++){
		int a;
		cin>>a;
		cout<<ans[a]<<endl;
	}
}

• 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: 0 / 11