# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
572401 | 2022-06-04T10:37:01 Z | MODDI | Pilot (NOI19_pilot) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> #define vl vector<ll> #define mp make_pair #define pb push_back using namespace std; const int maxn = 1e6 + 5; int n, q; 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; re -= sz[a] * (sz[a]+1) / 2; re -= sz[b] * (sz[b]+1) / 2; sz[a] += sz[b]; re += sz[a] * (sz[a]+1) / 2; par[b] = a; } vl G[maxn]; ll ans[maxn]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 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; } }