oj.uz

Submission #1090215

# Submission time Handle Problem Language Result Execution time Memory
1090215 2024-09-18T03:18:44 Z eysbutno Sails (IOI07_sails) C++17
100 / 100
 65 ms 3164 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

template<typename T> struct FenwickTree {
    int n; vector<T> arr;
    FenwickTree(int _n) : n(_n + 1), arr(n) {}

    /** @return sum on [0, idx] */
    T pre(int idx) {
        T tot = 0;
        for (++idx; idx > 0; idx -= idx & -idx) {
            tot += arr[idx];
        }
        return tot;
    }

    /** changes the location at idx by dx */
    void upd(int idx, T dx) {
        for (++idx; idx < n; idx += idx & -idx) {
            arr[idx] += dx;
        }
    }

    /** @return sum on [l, r] */
    T qry(int l, int r) { return pre(r) - pre(l - 1); }
};

template <typename T, typename F> 
T first_true(T low, T high, const F &fn) {
    while (low < high) {
        T mid = low + (high - low) / 2;
        fn(mid) ? high = mid : low = mid + 1;
    }
    return low;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    vector<int> h(n), k(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i] >> k[i];
    }
    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) -> bool {
        return h[i] < h[j];
    });
    const int MX = *max_element(all(h));
    FenwickTree<int> ft(MX + 1);
    for (int i : ord) {
        int last = h[i] - k[i];
        int val = ft.pre(last);
        if (last == 0 || ft.pre(last - 1) != val) {
            ft.upd(last, 1);
            ft.upd(h[i], -1);
        } else {
            int idx_1 = first_true(0, h[i], [&](int x) -> bool {
                return ft.pre(x) < val;
            });
            int idx_2 = first_true(0, h[i], [&](int x) -> bool {
                return ft.pre(x) <= val;
            });
            ft.upd(idx_1, 1);
            ft.upd(h[i], -1);
            ft.upd(idx_2, 1);
            ft.upd(idx_2 + k[i] - (h[i] - idx_1), -1);
        }
    }   
    ll res = 0;
    for (int i = 0; i < MX; i++) {
        int cnt = ft.pre(i);
        res += 1ll * cnt * (cnt - 1) / 2;
    }
    cout << res << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 13 ms 876 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1260 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1628 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2396 KB Output is correct
2 Correct 46 ms 2648 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2908 KB Output is correct
2 Correct 54 ms 2392 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3164 KB Output is correct
2 Correct 44 ms 2652 KB Output is correct