Submission #1143822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143822		mattsoh	Pilot (NOI19_pilot)	C++20	8 / 100	1096 ms	4476 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];
vector<pair<ll,ll>> rgs;
pair<ll,ll> p[maxn];
void rem(ll idx ){
    ll l = 0, r = rgs.size()-1;
    ll m;
    while (true){
        m = (l+r)/2;
        if (rgs[m].fi <= idx && idx <= rgs[m].se) break;
        if (m<idx){
            r = m;
        } else l = m;
    }
    pair<ll,ll> range = rgs[m];
    if (range.fi == idx){
        rgs[m].fi = idx+1;
    } else if (range.se == idx){
        rgs[m].se = idx-1;
    } else{
        rgs.insert(rgs.begin()+m+1,{idx+1,rgs[m].se});
        rgs[m].se = idx;
    }
    
}
signed main(){
    ll n,q;cin>>n>>q;
    for (ll i = 0;i<n;i++){
        ll hgt;cin>>hgt;
        h[i] = {hgt,i};
    }
    rgs.push_back({0,n});
    sort(h,h+n);
    reverse(h,h+n);
    // for (ll i = 0;i<n;i++){
    //     cout<<h[i].fi<<h[i].se<<endl;
    // }
    ll maxh = n, curr = 0;
    for (ll i = 0;i<q;i++){
        ll pl;cin>>pl;
        p[i] = {pl,i};
    }
    sort(p,p+q);
    reverse(p,p+q);
    for (ll i = 0;i<q;i++){
        ll plane = p[i].fi, ord = p[i].se;
        while (h[curr].fi > plane){
            // cout<<"removing"<<h[curr].fi<<h[curr].se<<endl;
            rem(h[curr].se);
            curr++;
        }
        ll total = 0;
        for (auto range:rgs){
            // cout<<"range"<<range.fi<<' '<<range.se<<endl;
            ll diff = range.se - range.fi;
            total += diff*(diff+1)/2;
        }
        p[i] = {ord, total};

    }
    sort(p,p+q);
    for (ll i = 0;i<q;i++)cout<<p[i].se<<endl;

}

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