Submission #1230490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230490		harryleee	Snowball (JOI21_ho_t2)	C++20	100 / 100	86 ms	9800 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
const long long inf = 1e18;
int n, q;
long long a[maxn + 1], v[maxn + 1], mx[maxn + 1], mn[maxn + 1], ans[maxn + 1];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    long long sum = 0;
    for (int i = 1; i <= q; ++i){
        cin >> v[i];
        sum += v[i];
        mx[i] = max(mx[i - 1], sum);
        mn[i] = min(mn[i - 1], sum);
    } 

    for (int i = 1; i <= n; ++i){
        int lo = 1, hi = q;
        long long res = 0;
        while (lo <= hi){
            int m = (lo + hi) >> 1;
            long long lb = a[i] + mn[m], rb = (i == 1) ? -inf : a[i - 1] + mx[m];
            res = max(res, a[i] - max(lb, rb));
            if (lb > rb) lo = m + 1;
            else hi = m - 1; 
        }
        ans[i] += res;

        lo = 1, hi = q, res = 0;
        while (lo <= hi){
            int m = (lo + hi) >> 1;
            long long rb = a[i] + mx[m], lb = (i == n) ? inf : a[i + 1] + mn[m];
            res = max(res, min(lb, rb) - a[i]);
            if (rb < lb) lo = m + 1;
            else hi = m - 1;
        }
        ans[i] += res;
    }
    
    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
    return 0;
}

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