#include<bits/stdc++.h>
using namespace std;
long long l[1000010];
long long r[1000010];
long long dp[1000010];
pair<long long,long long> a[1000010];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
long long n,q;
cin>>n>>q;
for(long long i=1;i<=n;i++){
cin>>a[i].first;
a[i].second=i;
}
sort(a+1,a+n+1);
for(long long i=1;i<=n;i++){
if(l[a[i].second-1]==0&&r[a[i].second+1]==0){
l[a[i].second]=a[i].second;
r[a[i].second]=a[i].second;
dp[i]=dp[i-1]+1;
}
else if(l[a[i].second-1]==0){
l[r[a[i].second+1]]=a[i].second;
r[a[i].second]=r[a[i].second+1];
dp[i]=r[a[i].second]-a[i].second+1+dp[i-1];
}
else if(r[a[i].second+1]==0){
r[l[a[i].second-1]]=a[i].second;
l[a[i].second]=l[a[i].second-1];
dp[i]=a[i].second-l[a[i].second]+1+dp[i-1];
}
else{
l[r[a[i].second+1]]=l[a[i].second-1];
r[l[a[i].second-1]]=r[a[i].second+1];
dp[i]=(a[i].second-l[a[i].second-1]+1)*(r[a[i].second+1]-a[i].second+1)+dp[i-1];
}
}
for(long long i=1;i<=q;i++){
long long x;
cin>>x;
long long l=0;
long long r=n;
while(l!=r){
long long mid=(l+r+1)/2;
if(x<a[mid].first)
r=mid-1;
else
l=mid;
}
cout<<dp[l]<<"\n";
}
}
# | 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... |