oj.uz

Submission #1095990

# Submission time Handle Problem Language Result Execution time Memory
1095990 2024-10-03T14:16:16 Z susanthenerd Sails (IOI07_sails) C++17
100 / 100
 70 ms 4632 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1120 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1456 KB Output is correct
2 Correct 17 ms 2076 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2136 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2900 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3928 KB Output is correct
2 Correct 43 ms 3900 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4300 KB Output is correct
2 Correct 33 ms 3892 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4632 KB Output is correct
2 Correct 37 ms 3932 KB Output is correct