Submission #1143885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143885		mattsoh	Pilot (NOI19_pilot)	C++20	89 / 100	114 ms	6400 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>> p(maxn);
set<pair<ll, ll>> rgs;
ll totalSum = 0;

void rem(ll idx) {
    auto it = rgs.lower_bound({idx, idx});
    if (it == rgs.end() || it->fi > idx) --it;

    pair<ll, ll> range = *it;
    rgs.erase(it);

    ll len = range.se - range.fi + 1;
    totalSum -= len * (len + 1) / 2;

    if (range.fi < idx) {
        ll leftLen = idx - range.fi;
        totalSum += leftLen * (leftLen + 1) / 2;
        rgs.insert({range.fi, idx - 1});
    }
    if (idx < range.se) {
        ll rightLen = range.se - idx;
        totalSum += rightLen * (rightLen + 1) / 2;
        rgs.insert({idx + 1, range.se});
    }
}

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;
}

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 - 1});
    totalSum = n * (n + 1) / 2;

    sort(h, h + n, cmpp);

    ll curr = 0;
    for (ll i = 0; i < q; i++) {
        ll pl;
        cin >> pl;
        p[i] = {pl, i};
    }

    sort(p.begin(), p.begin() + q, cmpp);

    vector<ll> result(q);
    for (ll i = 0; i < q; i++) {
        ll plane = p[i].fi, ord = p[i].se;

        while (curr < n && h[curr].fi > plane) {
            rem(h[curr].se);
            curr++;
        }

        result[ord] = totalSum;
    }

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

• 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