Submission #1119796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119796		Aviansh	Pilot (NOI19_pilot)	C++17	89 / 100	1057 ms	73804 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];
    map<int,vector<int>>mp;
    for(int i = 0;i<n;i++){
        cin >> h[i];
        mp[h[i]].push_back(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});
    map<int,vector<int>>::iterator las = mp.end();
    las--;
    bool wor = 1;
    for(int i = q-1;i>=0;i--){
        while(wor&&(*las).first>qs[i].first){
            for(int i : (*las).second){
                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(las==mp.begin()){
                wor=0;
            }
            las--;

        }
        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