# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
572409 | 2022-06-04T10:42:15 Z | MODDI | Pilot (NOI19_pilot) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define ll long long #define pb push_back #define endl '\n' 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; for(int i = 0; i < n; i++){ 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; } }