Submission #1095990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095990		susanthenerd	Sails (IOI07_sails)	C++17	100 / 100	70 ms	4632 KiB

sails

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

using namespace std;
using ll = long long;

constexpr ll VMAX = 1e5 + 1;

array<ll, VMAX> aib;

void add(ll i, ll d) {
    for (; i < VMAX; i += i & -i)
        aib[i] += d;
}

ll query(ll i) {
    ll ans = 0;
    for (; i > 0; i -= i & -i)
        ans += aib[i];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;

    vector<pair<ll, ll> > v(n);
    vector<ll> aib(1e5 + 1);


    for (auto &[h, k]: v)
        cin >> h >> k;


    sort(v.begin(), v.end(), [&](pair<ll, ll> a, pair<ll, ll> b) {
        if (a.first == b.first)
            return a.second > b.second;
        return a.first < b.first;
    });

    for (auto &[h, k]: v) {
        ll val = query(h - k + 1);
        ll st = 1, dr = h - k;

        while (st <= dr) {
            ll mij = (st + dr) / 2;
            if (query(mij) == val) {
                dr = mij - 1;
            } else {
                st = mij + 1;
            }
        }

        ll st2 = h - k + 2, dr2 = h;

        while (st2 <= dr2) {
            ll mij = (st2 + dr2) / 2;
            if (query(mij) == val) {
                st2 = mij + 1;
            } else {
                dr2 = mij - 1;
            }
        }

        add(st2, 1);
        add(h + 1, -1);
        k -= h - st2 + 1;
        add(st, 1);
        add(st + k, -1);
    }


    ll ans = 0;
    for (ll i = 1; i < VMAX; ++i) {
        ll x = query(i);
        ans += x * (x - 1) / 2;
    }

    cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10