oj.uz

Submission #784637

# Submission time Handle Problem Language Result Execution time Memory
784637 2023-07-16T11:22:04 Z borisAngelov Snowball (JOI21_ho_t2) C++17
0 / 100
 2 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const long long inf = 1e18;

int n, q;

long long a[maxn];

vector<pair<long long, int>> intervals;

long long ans[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    a[0] = -inf;
    a[n + 1] = +inf;

    for (int i = 1; i <= n + 1; ++i)
    {
        intervals.push_back(make_pair(a[i] - a[i - 1], i - 1));
    }

    sort(intervals.begin(), intervals.end());

    long long l = +inf;
    long long r = -inf;
    long long sum = 0;

    int ptr = 0;

    for (int i = 1; i <= q; ++i)
    {
        long long power;
        cin >> power;

        sum += power;

        l = min(l, sum);
        r = max(r, sum);

        while (r - l >= intervals[ptr].first)
        {
            if (power > 0)
            {
                ans[intervals[ptr].second] += intervals[ptr].first + l;
                ans[intervals[ptr].second + 1] -= l;
            }
            else
            {
                ans[intervals[ptr].second] += r;
                ans[intervals[ptr].second + 1] += intervals[ptr].first - r;
            }

            ++ptr;
        }
    }

    while (ptr < intervals.size())
    {
        ans[intervals[ptr].second] += r;
        ans[intervals[ptr].second + 1] -= l;
        ++ptr;
    }

    for (int i = 1; i <= n; ++i)
    {
        cout << ans[i] << "\n";
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     while (ptr < intervals.size())
      |            ~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 2 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 2 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -