Submission #502878

#	Time	Username	Problem	Language	Result	Execution time	Memory
502878		tabr	Sails (IOI07_sails)	C++17	100 / 100	115 ms	2864 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

template <typename T>
struct fenwick {
    int n;
    vector<T> node;

    fenwick(int _n) : n(_n) {
        node.resize(n);
    }

    void add(int x, T v) {
        while (x < n) {
            node[x] += v;
            x |= (x + 1);
        }
    }

    T get(int x) {  // [0, x]
        T v = 0;
        while (x >= 0) {
            v += node[x];
            x = (x & (x + 1)) - 1;
        }
        return v;
    }

    T get(int x, int y) {  // [x, y]
        return (get(y) - (x ? get(x - 1) : 0));
    }

    int lower_bound(T v) {
        int x = 0;
        int h = 1;
        while (n >= (h << 1)) {
            h <<= 1;
        }
        for (int k = h; k > 0; k >>= 1) {
            if (x + k <= n && node[x + k - 1] < v) {
                v -= node[x + k - 1];
                x += k;
            }
        }
        return x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    const int m = (int) 1e5 + 10;
    vector<int> a(m);
    for (int i = 0; i < n; i++) {
        int h, k;
        cin >> h >> k;
        a[h]--;
        a[h - k]++;
    }
    for (int i = 0; i < m - 1; i++) {
        a[i + 1] += a[i];
    }
    fenwick<int> cnt(m);
    fenwick<long long> sum(m);
    for (int i = m - 1; i >= 0; i--) {
        int lo = a[i] - 1;
        int hi = m - 1;
        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            long long t = sum.get(mid, m - 1) - cnt.get(mid, m - 1) * 1LL * mid;
            if (t <= mid - a[i]) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        int c = cnt.get(m - 1);
        int t = (int) (sum.get(hi, m - 1) - cnt.get(hi, m - 1) * 1LL * hi);
        a[i] += t;
        while (c != 0 && cnt.lower_bound(c) > hi) {
            int pos = cnt.lower_bound(c);
            int d = cnt.get(pos, pos);
            sum.add(pos, -1LL * pos * d);
            cnt.add(pos, -d);
            sum.add(hi, 1LL * hi * d);
            cnt.add(hi, d);
        }
        if (hi) {
            int d = hi - a[i];
            sum.add(hi, -d * 1LL * hi);
            sum.add(hi - 1, d * 1LL * lo);
            cnt.add(hi, -d);
            cnt.add(hi - 1, d);
            a[i] = hi;
        }
        cnt.add(a[i], 1);
        sum.add(a[i], a[i]);
    }
    long long ans = 0;
    for (int i = 2; i < m; i++) {
        ans += 1LL * cnt.get(i, i) * i * (i - 1) / 2;
    }
    cout << ans << '\n';
    return 0;
}

• 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