This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back
void solve() {
ll n,q;
cin>>n>>q;
pii h[n], y[q];
for (int i=0;i<n;i++){
cin>>h[i].fs;
h[i].sc=i;
}
for (int i=0;i<q;i++){
cin>>y[i].fs;
y[i].sc=i;
}
sort(h,h+n);
reverse(h,h+n);
sort(y,y+q);
reverse(y,y+q);
ll ans[q];
set<int> r;
r.insert(n-1);
r.insert(-1);
ll idx=0,last=1e6+1,cnt=n*(n+1)/2;
for (int i=0;i<q;i++){
while(last>y[i].fs+1){
last--;
while(h[idx].fs==last){
auto it=r.lower_bound(h[idx].sc);
ll a,b,c;
a=*it;
it--;
b=*it;
c=h[idx].sc;
cnt-=(a-b)*(a-b+1)/2;
cnt+=(a-c)*(a-c+1)/2;
cnt+=(c-b-1)*(c-b)/2;
r.insert(c);
r.insert(c-1);
idx++;
}
}
ans[y[i].sc]=cnt;
}
for (int i=0;i<q;i++)cout<<ans[i]<<'\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
# | 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... |