# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1187266 | aladdin1 | Pilot (NOI19_pilot) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
const int MAX = 1e6 + 100, MOD = 1e9 + 7;
vector<int> v[MAX];
vector<int> mp[MAX];
int ANS[MAX];
void solve(){
int n, q; cin >> n >> q;
int arr[n + 2];
for(int i = 1; i <= n; ++i){
cin >> arr[i];
mp[arr[i]].push_back(i);
}
unordered_set<int> st;
int ans = 0;
for(int i = 0; i <= n + 1; ++i){
st.insert(i);
}
for(int y = 0; y < MAX; ++y){
for(int i:mp[y]){
st.erase(i);
auto itr = st.lower_bound(i);
int j = *itr;
--itr;
int k = *itr;
int d1 = (i - k - 1);
int d2 = (j - i - 1);
int d3 = (j - k - 1);
ans -= d1 * (d1 + 1) / 2;
ans -= d2 * (d2 + 1) / 2;
ans += d3 * (d3 + 1) / 2;
}
ANS[y] = ans;
}
for(int i = 0; i < q; ++i){
int y; cin >> y;
cout << ANS[y] << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}