Submission #836765

#	Time	Username	Problem	Language	Result	Execution time	Memory
836765		vjudge1	Snowball (JOI21_ho_t2)	C++17	100 / 100	87 ms	16972 KiB

Main

#include <bits/stdc++.h>
using namespace std;

// 123
int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, q;
        cin >> n >> q;
        vector<int64_t> a(n), b(q);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < q; i++) cin >> b[i];
        vector<int64_t> mx(q + 1), mn(q + 1), sum(q + 1);
        int64_t cur = 0;
        for (int i = 0; i < q; i++) {
                cur += b[i];
                mx[i + 1] = max(mx[i], cur);
                mn[i + 1] = min(mn[i], cur);
                sum[i + 1] = mx[i + 1] - mn[i + 1];
        }
        vector<int64_t> res(n);
        res[0] -= mn[q];
        res[n - 1] += mx[q];
        for (int i = 0; i < n - 1; i++) {
                int64_t d = a[i + 1] - a[i];
                int l = 0, r = q, ans = -1;
                while (l <= r) {
                        int mid = l + r >> 1;
                        if (sum[mid] > d) {
                                ans = mid;
                                r = mid - 1;
                        } else {
                                l = mid + 1;
                        }
                }
                if (ans == -1) {
                        res[i] += mx[q];
                        res[i + 1] -= mn[q];
                } else {
                        assert(ans > 0);
                        ans--;
                        res[i] += mx[ans];
                        res[i + 1] -= mn[ans];
                        int64_t& which = (b[ans] > 0) ? res[i] : res[i + 1];
                        which += d - sum[ans];
                }
        }
        for (int i = 0; i < n; i++) cout << res[i] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:28:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |                         int mid = l + r >> 1;
      |                                   ~~^~~

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