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