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 int long long
const int mxn =1000005;
int n,q,h[mxn],a[mxn],dp[mxn],L[mxn],R[mxn];
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>h[i];
for(int i=1;i<=q;i++)
cin>>a[i];
stack<int> s;
h[0]=h[n+1]=INT_MAX;
s.push(0);
for(int i=1;i<=n;i++)
{
while(h[s.top()]<h[i])
s.pop();
L[i]=s.top();
s.push(i);
}
while(!s.empty())s.pop();
s.push(n+1);
for(int i=n;i>=1;i--)
{
while(h[s.top()]<=h[i])
s.pop();
R[i]=s.top();
s.push(i);
}
for(int i=1;i<=n;i++)
dp[h[i]]+=(i-L[i])*(R[i]-i);
for(int i=1;i<=1000000;i++)
dp[i]+=dp[i-1];
for(int i=1;i<=q;i++)
cout<<dp[a[i]]<<"\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... |