oj.uz

Submission #685281

# Submission time Handle Problem Language Result Execution time Memory
685281 2023-01-23T21:43:13 Z finn__ Sails (IOI07_sails) C++17
100 / 100
 220 ms 7324 KB 
#include <bits/stdc++.h>
using namespace std;

struct SegmentTreeRURQ
{
    vector<uint64_t> t, z;
    size_t l;

    SegmentTreeRURQ(size_t n)
    {
        l = 1 << (32 - __builtin_clz(n));
        t = vector<uint64_t>(2 * l, 0);
        z = vector<uint64_t>(2 * l, 0);
    }

private:
    void propagate(size_t k, size_t x, size_t y)
    {
        t[2 * k] += z[k] * (y - x + 1) / 2;
        t[2 * k + 1] += z[k] * (y - x + 1) / 2;
        z[2 * k] += z[k];
        z[2 * k + 1] += z[k];
        z[k] = 0;
    }

    void increment_r(size_t i, size_t j, size_t k, size_t x, size_t y)
    {
        if (x > y || y < i || x > j)
            return;
        if (i <= x && y <= j)
        {
            t[k] += y - x + 1;
            z[k]++;
        }
        else
        {
            propagate(k, x, y);
            increment_r(i, j, 2 * k, x, (x + y) / 2);
            increment_r(i, j, 2 * k + 1, (x + y) / 2 + 1, y);
            t[k] = t[2 * k] + t[2 * k + 1];
        }
    }

    uint64_t sum_r(size_t i, size_t j, size_t k, size_t x, size_t y)
    {
        if (x > y || y < i || x > j)
            return 0;
        if (i <= x && y <= j)
            return t[k];

        propagate(k, x, y);
        return sum_r(i, j, 2 * k, x, (x + y) / 2) + sum_r(i, j, 2 * k + 1, (x + y) / 2 + 1, y);
    }

public:
    void increment(size_t i, size_t j) { increment_r(i, j, 1, 0, l - 1); }

    uint64_t sum(size_t i, size_t j) { return sum_r(i, j, 1, 0, l - 1); }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n;
    cin >> n;

    unsigned max_h = 0;
    vector<pair<unsigned, unsigned>> masts(n);
    for (auto &[h, k] : masts)
    {
        cin >> h >> k;
        max_h = max(max_h, h);
    }
    sort(masts.begin(), masts.end());

    set<pair<unsigned, unsigned>> intervals;
    SegmentTreeRURQ tree(max_h + 1);
    unsigned last_h = 1;

    for (auto &[h, k] : masts)
    {
        if (h >= last_h)
        {
            intervals.emplace(last_h, min(h, last_h + k - 1));
            last_h = min(h + 1, last_h + k);
        }

        auto it = intervals.lower_bound(make_pair(last_h - k, last_h - k));
        if (it != intervals.end())
        {
            tree.increment(it->first, last_h - 1);
            k -= last_h - it->first;
            if (it != intervals.begin() && tree.sum(it->first, it->first) == tree.sum(it->first - 1, it->first - 1))
            {
                auto jt = it;
                jt--;
                pair<unsigned, unsigned> merged = make_pair(jt->first, it->second);
                intervals.erase(it);
                intervals.erase(jt);
                it = ++intervals.insert(merged).first;
            }
        }

        if (k && it != intervals.begin())
        {
            it--;
            auto const [a, b] = *it;
            intervals.erase(it);
            tree.increment(a, a + k - 1);
            it = intervals.emplace(a, a + k - 1).first;
            intervals.emplace(a + k, b);

            if (it != intervals.begin() && tree.sum(it->first, it->first) == tree.sum(it->first - 1, it->first - 1))
            {
                auto jt = it;
                jt--;
                pair<unsigned, unsigned> merged = make_pair(jt->first, it->second);
                intervals.erase(it);
                intervals.erase(jt);
                it = ++intervals.insert(merged).first;
            }
        }
    }

    uint64_t total_inefficiency = 0;
    for (unsigned i = 1; i <= max_h; i++)
    {
        uint64_t const x = tree.sum(i, i);
        if (x)
            total_inefficiency += (x * (x - 1)) / 2;
    }
    cout << total_inefficiency << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 18 ms 4436 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1524 KB Output is correct
2 Correct 40 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2848 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 3184 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 5244 KB Output is correct
2 Correct 151 ms 6676 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 7324 KB Output is correct
2 Correct 88 ms 5844 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 5868 KB Output is correct
2 Correct 131 ms 3176 KB Output is correct