Submission #1308646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308646		VMaksimoski008	Snowball (JOI21_ho_t2)	C++20	100 / 100	1685 ms	6728 KiB

Main

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

int find_first(vector<ll> &a, ll x) {
    int l=1, r=a.size()-1, ans=1e9;
    while(l <= r) {
        int m = (l + r) / 2;
        if(a[m] >= x) ans = m, r = m - 1;
        else l = m + 1;
    }
    return ans;
}

signed main() {
    int n, q; cin >> n >> q;

    vector<ll> a(n+2);
    for(int i=1; i<=n; i++) cin >> a[i];

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

    ll cur = 0;
    vector<ll> mn(q+1), mx(q+1);
    for(int i=1; i<=q; i++) {
        ll x; cin >> x;

        cur += x;
        mn[i] = max(mn[i-1], -cur);
        mx[i] = max(mx[i-1], cur);
    }

    for(int i=1; i<=n; i++) {
        ll L=a[i], R=a[i];

        ll l=a[i-1], r=a[i]-1;
        while(l <= r) {
            ll mid = (l + r) / 2;

            if(find_first(mn, a[i] - mid) < find_first(mx, mid - a[i-1] + 1))
                L = mid, r = mid - 1;
            else
                l = mid + 1;
        }

        l=a[i]+1, r=a[i+1];
        while(l <= r) {
            ll mid = (l + r) / 2;

            if(find_first(mx, mid - a[i]) < find_first(mn, a[i+1] - mid + 1))
                R = mid, l = mid + 1;
            else
                r = mid - 1;
        }


        cout << R - L << '\n';
    }
}

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