Submission #1143931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143931		mattsoh	Pilot (NOI19_pilot)	C++17	51 / 100	120 ms	11288 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const ll maxn = 1e5+10;
pair<ll,ll> h[maxn],p[maxn];
set<pair<ll,ll>> rgs;
ll summ=0, ans[maxn];
bool cmpp(pair<ll,ll>t1,pair<ll,ll>t2){
    if (t1.fi!=t2.fi) return t1.fi>t2.fi;
    else return t1.se<t2.se;
}
void rem(ll idx ){
    auto it = rgs.lower_bound({idx, idx+1});
    if (it == rgs.end() || it->fi > idx) {
        if (it == rgs.begin()) return;
        it--;
    }

    pair<ll,ll> range = *it;
    rgs.erase(it);
    ll len = range.se - range.fi;
    summ -= len * (len + 1) / 2;
    if (range.fi < idx) {
        ll leftLen = idx - range.fi;
        summ += leftLen * (leftLen + 1) / 2;
        rgs.insert({range.fi, idx});
    }
    if (idx < range.se) {
        ll rightLen = range.se - idx - 1;
        summ += rightLen * (rightLen + 1) / 2;
        rgs.insert({idx + 1, range.se});
    }
    
}
signed main(){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
    ll n,q;cin>>n>>q;
    for (ll i = 0;i<n;i++){
        ll hgt;cin>>hgt;
        h[i] = {hgt,i};
    }
    rgs.insert({0,n});
    sort(h,h+n,cmpp);
    // reverse(h,h+n);
    // for (ll i = 0;i<n;i++){
    //     cout<<h[i].fi<<h[i].se<<endl;
    // }
    summ =n * (n + 1) / 2;
    ll maxh = n, curr = 0;
    for (ll i = 0;i<q;i++){
        ll pl;cin>>pl;
        p[i] = {pl,i};
    }
    sort(p,p+q,cmpp);
    for (ll i = 0;i<q;i++){
        ll plane = p[i].fi, ord = p[i].se;
        // cout<<"plane height "<<plane<<ord<<endl;
        if (plane == curr) {
            ans[ord] = ans[ord-1];
            continue;
        }
        while (curr < n && h[curr].fi > plane){
            // cout<<"removing"<<h[curr].fi<<h[curr].se<<endl;
            rem(h[curr].se);
            curr++;
        }
        // for (auto r:rgs) cout<<"ranges"<<r.fi<<r.se<<endl;
        ans[ord] = summ;

    }
    for (ll i = 0;i<q;i++)cout<<ans[i]<<endl;

}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11