Submission #1340099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340099		mantaggez	Pilot (NOI19_pilot)	C++20	100 / 100	926 ms	61940 KiB

pilot

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

const ll nx = 1e6+5;
const ll INF = 1e18;

ll n, q, res, ans[nx];
vector<pii> h, y;
set<pii> s;

void add(ll l, ll r)
{
    s.insert({l, r});
    res += (r - l + 1) * (r - l + 2) / 2;
}

void del(ll l, ll r)
{
    s.erase({l, r});
    res -= (r - l + 1) * (r - l + 2) / 2;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> q;
    for(ll i=1;i<=n;i++) {
        ll x; cin >> x;
        h.push_back({x, i});
    }
    for(ll i=1;i<=q;i++) {
        ll x; cin >> x;
        y.push_back({x, i});
    }
    sort(h.begin(), h.end(), greater<pii>());
    sort(y.begin(), y.end(), greater<pii>());
    add(1, n);
    for(ll j=0, i=0;j<q;j++) {
        while(h[i].first > y[j].first) {
            auto it = s.upper_bound({h[i].second, INF});
            if(it == s.begin()) continue;
            it--;
            auto [l, r] = *it;
            del(l, r);
            if(l <= h[i].second - 1) add(l, h[i].second - 1);
            if(h[i].second + 1 <= r) add(h[i].second + 1, r);
            i++;
        }
        ans[y[j].second] = res;
    }

    for(ll i=1;i<=q;i++) cout << ans[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: 11 / 11