Submission #638281

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638281	2022-09-05T08:03:20 Z	finn__	Sails (IOI07_sails)	C++17	0 / 100	1000 ms	4436 KB

sails

#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;
            if (range)
            {
                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:135:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'long int' [-Wsign-compare]
  135 |     for (size_t i = 0; i <= hmax; i++)
      |                        ~~^~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1084 ms	212 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 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	Execution timed out	1089 ms	340 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1084 ms	920 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1082 ms	2508 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1089 ms	2784 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1085 ms	4292 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1088 ms	4436 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-