Submission #854149

#	Time	Username	Problem	Language	Result	Execution time	Memory
854149		BrineTw	Snowball (JOI21_ho_t2)	C++14	100 / 100	86 ms	11388 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#define debug(x) cerr << #x << ' ' << x << '\n'
#define endl '\n'

using namespace std;

const int M = 1e9 + 7;
typedef long long ll;


int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N, Q;
    cin >> N >> Q;

    vector<ll> x(N);
    vector<ll> w(Q);
    for (auto& n: x) cin >> n;
    for (auto& n: w) cin >> n;

    vector<ll> snow(N - 1);
    for (int i = 1; i < N; i++) {
        snow[i - 1] = x[i] - x[i - 1];
    }

    vector<ll> left(Q + 1);
    vector<ll> right(Q + 1);
    
    ll cur = 0;
    for (int i = 1; i <= Q; i++) {
        cur += w[i - 1];
        left[i] = min(left[i - 1], cur);
        right[i] = max(right[i - 1], cur);
    }
    for (int i = 0; i <= Q; i++) {
        left[i] = abs(left[i]);
    }

    vector<ll> ans(N);
    for (int i = 0; i < N - 1; i++) {
        ll l = 0, m, r = Q;
        while (r - l > 1) {
            m = l + r >> 1;
            (left[m] + right[m] < snow[i] ? l : r) = m;
        }
        
        ans[i] += right[l];
        ans[i + 1] += left[l];

        if (w[l] < 0) {
            ans[i + 1] -= left[l];
            ans[i + 1] += min(left[r], snow[i] - right[r]);
        } else {
            ans[i] -= right[l];
            ans[i] += min(right[r], snow[i] - left[r]);
        }
    }

    ans[0] += left.back();
    ans.back() += right.back();

    for (auto& n: ans) cout << n << '\n';

    return 0;   
}

Compilation message (stderr)

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

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