#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#define pii pair<int , int>
using namespace std;
const int N = 1e6 + 1;
int h[N];
vector<int> adj[N];
vector<pii> queries;
int n , q;
int check[N];
long long ans[N];
long long res = 0;
struct DSU{
int sz[N];
int par[N];
void init(void){
for(int i = 1 ; i <= n ; i++){
sz[i] = 1;
par[i] = i;
}
}
int find(int u){
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
void joinset(int u , int v){
u = find(u);
v = find(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u , v);
res -= ((sz[u] + 1) * sz[u] / 2 + (sz[v] + 1) * (sz[v]) / 2);
sz[u] += sz[v];
par[v] = u;
res += (sz[u] + 1) * sz[u] / 2;
}
} dsu;
void solve(void){
cin >> n >> q;
for(int i = 1; i <= n ; i++) cin >> h[i];
for(int i = 1 ; i <= q ; i++){
int w; cin >> w;
queries.push_back(make_pair(w, i));
}
sort(queries.begin() , queries.end());
for(int i = 1 ; i <= n ; i++){
int pos = lower_bound(queries.begin() , queries.end() , make_pair(h[i] , 0)) - queries.begin();
adj[queries[pos].second].push_back(i);
}
dsu.init();
for(int i = 1 ; i <= n ; i++) check[i] = -1;
for(int i = 0 ; i <= q - 1; i++){
for(auto x : adj[queries[i].second]){
if(check[x] == -1){
res++;
check[x] = 1;
}
//cerr << "Debug" << " " << check[x] << " " << queries[i].first << " " << queries[i].second << " " << res << endl;
if(x + 1 <= n && h[x + 1] <= queries[i].first) dsu.joinset(x , x + 1);
if(x - 1 >= 1 && h[x - 1] <= queries[i].first) dsu.joinset(x , x - 1);
}
ans[queries[i].second] = res;
}
for(int i = 1 ; i <= q ; i++) cout << ans[i] << endl;
}
signed main(void){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |