Submission #1119868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119868		Aviansh	Pilot (NOI19_pilot)	C++17	89 / 100	1049 ms	49816 KiB

pilot

#include <bits/stdc++.h>

using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    int h[n];
    priority_queue<pair<int,int>>pq;
    for(int i = 0;i<n;i++){
        cin >> h[i];
        pq.push({h[i],i});
    }
    pair<int,int> qs[q];
    for(int i = 0;i<q;i++){
        int y;
        cin >> y;
        qs[i]={y,i};
    }
    sort(qs,qs+q);
    long long ans[q];
    long long currans = ((1LL*n*(n-1))/2)+n;
    set<pair<int,int>>rangs;
    rangs.insert({0,n-1});
    bool wor = 1;
    for(int i = q-1;i>=0;i--){
        while(wor&&pq.top().first>qs[i].first){
            int i = pq.top().second;
            pq.pop();
            set<pair<int,int>>::iterator it = (--rangs.upper_bound({i,2e9}));
            pair<int,int>p = *it;
            int len = p.second-p.first+1;
            currans-=((1LL*len*(len-1))/2)+len;
            rangs.erase(it);
            if(p.first!=i){
                rangs.insert({p.first,i-1});
                len = i-p.first;
                currans+=((1LL*len*(len-1))/2)+len;
            }
            if(p.second!=i){
                rangs.insert({i+1,p.second});
                len = p.second-i;
                currans+=((1LL*len*(len-1))/2)+len;
            }
            if(pq.size()==0){
                wor=0;
            }
        }
        ans[qs[i].second]=currans;
    }
    for(long long i : ans){
        cout << i << "\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: 0 / 11