oj.uz

Submission #502878

# Submission time Handle Problem Language Result Execution time Memory
502878 2022-01-06T16:52:14 Z tabr Sails (IOI07_sails) C++17
100 / 100
 115 ms 2864 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 1876 KB Output is correct
2 Correct 60 ms 1868 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 1876 KB Output is correct
2 Correct 60 ms 1876 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1844 KB Output is correct
2 Correct 65 ms 1872 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1872 KB Output is correct
2 Correct 64 ms 1988 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1892 KB Output is correct
2 Correct 75 ms 1880 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1868 KB Output is correct
2 Correct 75 ms 2172 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2428 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 2632 KB Output is correct
2 Correct 109 ms 2788 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 2740 KB Output is correct
2 Correct 98 ms 2580 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 2676 KB Output is correct
2 Correct 112 ms 2864 KB Output is correct