Submission #1123491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123491		LucaIlie	Snowball (JOI21_ho_t2)	C++20	100 / 100	2463 ms	6768 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
const int MAX_Q = 2e5;
int n, q;
const long long INF = 1e18;
long long x[MAX_N + 2], minSum[MAX_Q + 1], maxSum[MAX_Q + 1];

long long getTimeRight( int i, long long y ) {
    long long l = 0, r = q + 1;
    while ( r - l > 1 ) {
        long long t = (l + r) / 2;

        if ( x[i] + maxSum[t] >= y )
            r = t;
        else
            l = t;
    }
    return r;
}

long long getTimeLeft( int i, long long y ) {
    long long l = 0, r = q + 1;
    while ( r - l > 1 ) {
        long long t = (l + r) / 2;

        if ( x[i] + minSum[t] <= y )
            r = t;
        else
            l = t;
    }
    return r;
}

int main() {
    cin >> n >> q;
    x[0] = -INF;
    for ( int i = 1; i <= n; i++ )
        cin >> x[i];
    x[n + 1] = INF;
    long long sum = 0;
    minSum[0] = maxSum[0] = 0;
    for ( int t = 1; t <= q; t++ ) {
        long long w;
        cin >> w;
        sum += w;
        minSum[t] = min( minSum[t - 1], sum );
        maxSum[t] = max( maxSum[t - 1], sum );
    }

    for ( int i = 1; i <= n; i++ ) {
        long long l, r;
        long long ans = 0;


        l = x[i] + minSum[q] - 1, r = x[i];
        while ( r - l > 1 ) {
            long long mid = (l + r) / 2;

            if ( getTimeLeft( i, mid ) < getTimeRight( i - 1, mid + 1 ) )
                r = mid;
            else
                l = mid;
        }
        ans += x[i] - r;

        l = x[i], r = x[i] + maxSum[q] + 1;
        while ( r - l > 1 ) {
            long long mid = (l + r) / 2;

            if ( getTimeRight( i, mid ) < getTimeLeft( i + 1, mid - 1 ) )
                l = mid;
            else
                r = mid;
        }
        ans += l - x[i];

        cout << ans << "\n";
    }
}

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