oj.uz

Submission #685280

# Submission time Handle Problem Language Result Execution time Memory
685280 2023-01-23T21:39:23 Z finn__ Sails (IOI07_sails) C++17
15 / 100
 193 ms 8136 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--;
            tree.increment(it->first, it->first + k - 1);
            intervals.emplace(it->first, it->first + k - 1);
            intervals.emplace(it->first + k, it->second);
            intervals.erase(it);
        }
    }

    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 1 ms 216 KB Output is correct
2 Correct 0 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 1 ms 212 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 3152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 4240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 7188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 8136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 8076 KB Output isn't correct
2 Halted 0 ms 0 KB -