Submission #1312483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312483		aryan	Pilot (NOI19_pilot)	C++20	100 / 100	378 ms	38748 KiB

pilot

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


int main(){
        
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q;
    vector<pair<int,int>> a(n);
    for(int i = 0;i < n;i++){
        cin >> a[i].first;
        a[i].second = i;
    }

    vector<int> pg(n,-1);
    vector<int> ng(n,n);

    {
        stack<int> st;
        for(int i = 0;i < n;i++){
            while(!st.empty() && a[st.top()].first < a[i].first) st.pop();
            if(!st.empty()) pg[i] = st.top();
            st.push(i);
        }
    }


    {
        stack<int> st;
        for(int i = n - 1;i >= 0;i--){
            while(!st.empty() && a[st.top()].first <= a[i].first) st.pop();
            if(!st.empty()) ng[i] = st.top();
            st.push(i);
        }
    }

    sort(a.begin(),a.end(),greater<pair<int,int>>());
    
    vector<pair<int,int>> que(q);
    for(int i = 0;i < q;i++){
        cin >> que[i].first;
        que[i].second = i;
    }
    sort(que.begin(),que.end(),greater<pair<int,int>>());
    
    int j = 0;
    i64 cur = n * 1LL * (n + 1);
    cur /= 2;
    vector<i64> ans(q);
    for(int i = 0;i < q;i++){
        int e = que[i].second;
        int x = que[i].first;
        while(j < n && a[j].first > x){
            int ind = a[j].second; 
            int l = pg[ind];
            int r = ng[ind];
            l ++;
            r --;
            assert(r >= l && l <= ind);
            i64 bad = (ind - l + 1) * 1LL * (r - ind + 1);
            cur -= bad;
            j ++;
        }
        ans[e] = cur;
    }
    for(int i = 0;i < q;i++){
        cout << ans[i] << " ";
    }
    cout << '\n';
    return 0;
}

• 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