Submission #937882

#	Time	Username	Problem	Language	Result	Execution time	Memory
937882		zwezdinv	Snowball (JOI21_ho_t2)	C++17	100 / 100	66 ms	15300 KiB

Main

#include <bits/stdc++.h>

int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n, q;
        std::cin >> n >> q;
        std::vector<long long> a(n);
        for (auto& i : a) std::cin >> i;
        std::vector<std::pair<long long, int>> b;
        for (int i = 0; i < n - 1; ++i) {
                b.emplace_back(a[i + 1] - a[i], i);
        }
        std::sort(b.begin(), b.end());
        std::vector<long long> lb(n, -1e18), rb(n, 1e18);
        std::pair<long long, long long> seg = {0, 0};
        long long cur = 0;
        for (int i = 0, j = 0; i < q; ++i) {
                auto nw = seg;
                long long x;
                std::cin >> x;
                cur += x;
                nw.first = std::min(nw.first, cur);
                nw.second = std::max(nw.second, cur);
                while (j < b.size() && b[j].first <= nw.second - nw.first) {
                        int k = b[j].second;
                        if (cur > 0) {
                                rb[k] = a[k + 1] + seg.first;
                                lb[k + 1] = rb[k];
                        } else {
                                lb[k + 1] = a[k] + seg.second;
                                rb[k] = lb[k + 1];
                        }
                        j++;
                }
                seg = nw;
        }
        for (int i = 0; i < n; ++i) {
                lb[i] = std::max(lb[i], a[i] + seg.first);
                rb[i] = std::min(rb[i], a[i] + seg.second);
                std::cout << rb[i] - lb[i] << '\n';
        }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:26: 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]
   25 |                 while (j < b.size() && b[j].first <= nw.second - nw.first) {
      |                        ~~^~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67