Submission #1180300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180300		nekolie	Snowball (JOI21_ho_t2)	C++20	100 / 100	199 ms	9952 KiB

Main

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,q; cin >> n >> q;
    long long x[n], jump[q+1], maks[q+1], mini[q+1], odp[n];
    for (int i = 0; i < n; i++)
        cin >> x[i], odp[i] = 0;
    jump[0] = maks[0] = mini[0] = 0;
    for (int i = 1; i <= q; i++)
        cin >> jump[i], jump[i] += jump[i-1], maks[i] = max(maks[i-1],jump[i]), mini[i] = min(mini[i-1],jump[i]);
    odp[0] = -mini[q], odp[n-1] = maks[q];
    for (int i = 1; i < n; i++) {
        if (x[i-1]+maks[q] <= x[i]+mini[q])
            odp[i-1] += maks[q], odp[i] -= mini[q];
        else {
            int l = 1, r = q;
            while (l < r) {
                int s = (l+r)/2;
                if (x[i-1]+maks[s] > x[i]+mini[s])
                    r = s;
                else
                    l = s+1;
            }
            odp[i-1] += maks[l-1], odp[i] -= mini[l-1];
            if (jump[l] > jump[l-1])
                odp[i-1] += (x[i]-x[i-1])-(maks[l-1]-mini[l-1]);
            else
                odp[i] += (x[i]-x[i-1])-(maks[l-1]-mini[l-1]);
        }
    }
    for (int i = 0; i < n; i++)
        cout << odp[i] << endl;
    return 0;
}

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