Submission #685281

#	Time	Username	Problem	Language	Result	Execution time	Memory
685281		finn__	Sails (IOI07_sails)	C++17	100 / 100	220 ms	7324 KiB

sails

#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 / 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