Submission #1325466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325466		polishprogrammer	Snowball (JOI21_ho_t2)	C++20	100 / 100	908 ms	8420 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lld long double
int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    ll w, ak = 0, p = 0, l = 0;
    vector<ll> poz(n);
    vector<pair<ll, int>> lewo, prawo;
    prawo.pb({0, 0});
    lewo.pb({0, 0});
    for (int i = 0; i < n; i++) cin >> poz[i];
    for (int i = 1; i <= q; i++) {
        cin >> w;
        ak += w;
        if (ak > p) {
            prawo.pb({ak, i});
            p = ak;
        }
        if (ak < l) {
            lewo.pb({-ak, i});
            l = ak;
        }
    }
    vector<ll> wyn(n);
    wyn[0] = -l;
    wyn[n-1] += p;
    pair<ll, int> pa;
    int cz1, cz2;

    for (int i = 1; i < n; i++) {
        ll li = poz[i-1], pi = poz[i];
        ll pocz = 0, kon = pi - li, sr;

        if (-l + p < kon) {
            wyn[i-1] += p;
            wyn[i] += -l;
            continue;
        }

        while (pocz < kon) {
            sr = (pocz + kon + 1) / 2;
            pa = {sr, 0};
            auto it = lower_bound(prawo.begin(), prawo.end(), pa);
            if (it != prawo.end()) {
                pa = *it;
                cz1 = pa.se;
            }
            else cz1 = 1e9;
            pa = {pi - li - sr + 1, 0};
            it = lower_bound(lewo.begin(), lewo.end(), pa);
            if (it != lewo.end()) {
                pa = *it;
                cz2 = pa.se;
            }
            else cz2 = 1e9;

            if (cz1 < cz2) pocz = sr;
            else kon = sr - 1;
        }
        wyn[i-1] += pocz;
        wyn[i] += pi-li-pocz;
    }
    for (ll i : wyn) cout << i << endl;
}

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