oj.uz

답안 #638280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638280 2022-09-05T08:01:38 Z finn__ Sails (IOI07_sails) C++17
0 / 100
 826 ms 9920 KB 
#include <bits/stdc++.h>
using namespace std;

struct fenwick_tree
{
    vector<long> tree;
    size_t l;

    fenwick_tree(size_t n)
    {
        l = n;
        tree = vector<long>(1 << (32 - __builtin_clz(l)), 0);
    }

    void update(long i, long x)
    {
        i++;
        while (i <= tree.size())
        {
            tree[i - 1] += x;
            i += i & -i;
        }
    }

    void range_incr(long i, long j, long x)
    {
        update(i, x);
        if (j < l - 1)
            update(j + 1, -x);
    }

    long prefix_sum(long i)
    {
        i++;
        long x = 0;
        while (i)
        {
            x += tree[i - 1];
            i -= i & -i;
        }
        return x;
    }

    // Returns the leftmost element not greater.
    size_t lower_bound(long x)
    {
        size_t a = 1, b = l;
        while (a < b)
        {
            size_t mid = (a + b) / 2;
            if (prefix_sum(mid) > x)
                a = mid + 1;
            else
                b = mid;
        }
        return a;
    }
};

struct event
{
    long h, k, num;
};

bool event_earlier(event const &a, event const &b)
{
    return a.h < b.h;
}

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

    size_t n;
    cin >> n;

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

    vector<event> events;
    for (size_t i = 0; i < n; i++)
    {
        event curr = {masts[i].first, masts[i].second, 1};
        while (i < n - 1 && masts[i + 1].first == curr.h)
        {
            curr.k += masts[i + 1].second;
            curr.num++;
            i++;
        }
        events.push_back(curr);
    }

    fenwick_tree tree(hmax + 2);

    long prev_height = 0, prev_num = LONG_MAX;

    for (event e : events)
    {
        long k = e.k, h = e.h;
        long x = prev_height + 1, y = prev_num;
        while (k)
        {
            long range = h - x + 1;
            long diff = max(0L, min(y - tree.prefix_sum(x), min(k / range, e.num)));
            tree.range_incr(x, h, diff);
            k -= diff * range;

            // Check wheter it is sufficient to only increment some prefix of the current range.
            if (k <= range && (x == 1 || tree.prefix_sum(x - 1) > tree.prefix_sum(x)))
            {
                tree.range_incr(x, x + k - 1, 1);
                k = 0;
            }
            x = tree.lower_bound(y);
            if (x)
                y = tree.prefix_sum(x - 1);
            else
                y = LONG_MAX;
        }
        prev_height = h;
        prev_num = tree.prefix_sum(h);
    }

    int64_t total_num = 0;
    for (size_t i = 0; i <= hmax; i++)
    {
        long x = tree.prefix_sum(i);
        total_num += x * (x - 1) / 2;
    }

    cout << total_num << '\n';
}

Compilation message

sails.cpp: In member function 'void fenwick_tree::update(long int, long int)':
sails.cpp:18:18: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         while (i <= tree.size())
      |                ~~^~~~~~~~~~~~~~
sails.cpp: In member function 'void fenwick_tree::range_incr(long int, long int, long int)':
sails.cpp:28:15: warning: comparison of integer expressions of different signedness: 'long int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if (j < l - 1)
      |             ~~^~~~~~~
sails.cpp: In function 'int main()':
sails.cpp:132:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'long int' [-Wsign-compare]
  132 |     for (size_t i = 0; i <= hmax; i++)
      |                        ~~^~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1816 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 826 ms 2000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 5404 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 6476 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 9468 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 9920 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -