Submission #852325

#	Time	Username	Problem	Language	Result	Execution time	Memory
852325		Mularstyle	Pilot (NOI19_pilot)	C++14	100 / 100	219 ms	60128 KiB

pilot

#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";

}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11