Submission #660158

#	Time	Username	Problem	Language	Result	Execution time	Memory
660158		beepbeepsheep	Pilot (NOI19_pilot)	C++17	100 / 100	325 ms	36684 KiB

pilot

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define endl '\n'
typedef pair<ll,ll> ii;
const ll inf=1e15;
const ll mod=1e9+7;
const ll maxn=1e6+5;

ll ans[maxn];
ll arr[maxn];
stack<ll> s;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    s.push(0);
    ll n,q,ele;
    cin>>n>>q;
    for (int i=1;i<=n;i++){
        cin>>arr[i];
    }
    arr[0]=inf;
    arr[n+1]=inf;
    for (int i=1;i<=n+1;i++){
        while (arr[s.top()]<arr[i]){
            ll a=s.top();
            s.pop();
            ans[arr[a]]+=(i-s.top()-1)*(i-s.top())/2;
            if (i==n+1 && s.top()==0) break;
            ans[min(arr[i],arr[s.top()])]-=(i-s.top()-1)*(i-s.top())/2;
        }
        s.push(i);
    }
    for (int i=1;i<=maxn;i++){
        ans[i]+=ans[i-1];
    }
    for (int i=0;i<q;i++){
        cin>>ele;
        cout<<ans[ele]<<endl;
    }
    return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:37:15: warning: iteration 1000004 invokes undefined behavior [-Waggressive-loop-optimizations]
   37 |         ans[i]+=ans[i-1];
      |         ~~~~~~^~~~~~~~~~
pilot.cpp:36:19: note: within this loop
   36 |     for (int i=1;i<=maxn;i++){
      |                  ~^~~~~~

• 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