Submission #1312476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312476		aryan	Pilot (NOI19_pilot)	C++20	100 / 100	893 ms	77412 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;
    }
    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;
    set<int> st;
    st.insert(-1);
    st.insert(n);
    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; 
            auto ir = st.upper_bound(ind);
            auto il = ir;
            il --;
            int l = *il;
            int r = *ir;
            l ++;
            r --;
            assert(r >= l && l <= ind);
            i64 bad = (ind - l + 1) * 1LL * (r - ind + 1);
            cur -= bad;
            st.insert(a[j].second);
            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