#include <bits/stdc++.h> #define ll long long #define pb push_back #define eb emplace_back #define pu push #define ins insert #define fi first #define se second #define all(a) a.begin(),a.end() #define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fu(x,a,b) for (auto x=a;x<=b;x++) #define fd(x,a,b) for (auto x=a;x>=b;x--) #define int ll using namespace std; //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); /* Competitive Programming notes that I need to study & fix my dumbass self: 1. Coding: - Always be sure to check the memory of arrays (maybe use vectors), for loops - Always try to maximize the memory if possible, even if you are going for subtasks - Do not exploit #define int long long, it will kill you 2. Stress: - Always try generating big testcases and try if they run 3. Time management: - Don't overcommit or undercommit, always spend a certain amount of time to think a problem, don't just look at it and say I'm fucked - Do not spend too much time coding brute-force solutions, they should be easily-codable solutions that don't take up too much time Time management schedule: Offline / LAH days (4 problems - 3h): 15' thinking of solution / idea 1. no idea: skip 2. yes idea: continue thinking for <= 15' + implementing: <= 20' + brute-force: <= 5' + test generator: <= 5' I hate offline because I am dumb */ typedef pair<int, int> ii; const int N = 1e6+5; const int B = 750; const int mod = 1e9+7; const int inf = 1e18; using cd = complex<double>; const long double PI = acos(-1); int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} int n,q; int a[N]; vector<ii> b, v; bool on[N]; int par[N], sz[N], l[N], r[N], ans = 0; int res[N]; int find(int u) { if (u == par[u]) return u; return par[u] = find(par[u]); } void merge(int u, int v) { u = find(u); v = find(v); if (u == v) return; ans -= sz[u] * (sz[u]+1) / 2 + sz[v] * (sz[v] + 1) / 2; sz[u] += sz[v]; par[v] = u; ans += sz[u] * (sz[u] + 1) / 2; } void add(int pos) { // cout<<pos<<endl; // return; on[pos] = 1; ans++; if (pos && on[find(pos-1)]) merge(pos-1, pos); if (pos < n-1 && on[find(pos+1)]) merge(pos+1, pos); } void solve() { cin>>n>>q; for (int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; l[i] = r[i] = i; ans = 0; } for (int i = 0; i < n; i++) cin>>a[i], v.pb({a[i], i}); for (int i = 1; i <= q; i++) { int y; cin>>y; b.pb({y, i}); } sort(all(b)); sort(all(v)); int j = -1; for (int i = 0; i < q; i++) { while (j < n-1 && v[j+1].fi <= b[i].fi) { j++; add(v[j].se); } res[b[i].se] = ans; } for (int i = 1; i <= q; i++) cout<<res[i]<<endl; } /* Go through the mistakes you usually make and revise your code, for god's sake... */ signed main() { bruh //freopen(".inp","r",stdin); //freopen(".out","w",stdout); int t = 1; // cin>>t; while (t--) { solve(); cout<<"\n"; } }