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>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N=1e6+5;
int n,q;
ll ans,qs[N],ansarr[N];
int arr[N],qst[N],dp[N];
set<int>st;
priority_queue<pii,vector<pii>,greater<pii>>pq;
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n >> q;
for(int i=1; i<=n; i++){
cin >> arr[i];
qs[i]=qs[i-1]+i;
pq.push({arr[i],i});
}
for(int i=1; i<=q; i++){
cin >> qst[i];
st.insert(qst[i]);
}
for(auto it=st.begin(); it!=st.end(); it++){
while(!pq.empty()&&pq.top().first<=*it){
int h=pq.top().first;
int idx=pq.top().second;
pq.pop();
dp[idx]=idx;
int l=idx,r=idx;
if(dp[idx-1]){
ans-=qs[(idx-1)-dp[idx-1]+1];
int tmp=dp[idx-1];
dp[dp[idx-1]]=idx;
dp[idx]=tmp;
l=tmp;
}
if(dp[idx+1]){
ans-=qs[dp[idx+1]-(idx+1)+1];
int tmp=dp[idx+1];
dp[dp[idx+1]]=dp[idx];
dp[dp[idx]]=tmp;
r=dp[l];
}
ans+=qs[r-l+1];
}
ansarr[*it]=ans;
}
for(int i=1; i<=q; i++){
cout << ansarr[qst[i]] << '\n';
}
return 0;
}
Compilation message (stderr)
pilot.cpp: In function 'int main()':
pilot.cpp:27:17: warning: unused variable 'h' [-Wunused-variable]
27 | int h=pq.top().first;
| ^
# | 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... |