oj.uz

Submission #632167

# Submission time Handle Problem Language Result Execution time Memory
632167 2022-08-19T14:47:17 Z Ooops_sorry Snowball (JOI21_ho_t2) C++17
0 / 100
 7 ms 724 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const ll INF = 1e18;

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<ll> x(n), w(q), ans(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    ll cur = 0, mn = 0, mx = 0;
    vector<ll> u{-INF, INF};
    for (int i = 0; i < q; i++) {
        cin >> w[i];
        cur += w[i];
        mn = min(mn, cur);
        mx = max(mx, cur);
        u.pb(cur);
    }
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    int m = u.size();
    vector<int> pr(m, q), sf(m, q);
    cur = 0;
    for (int i = 0; i < q; i++) {
        cur += w[i];
        int j = lower_bound(u.begin(), u.end(), cur) - u.begin();
        pr[j] = min(pr[j], i);
        sf[j] = min(sf[j], i);
    }
    for (int i = 1; i < q; i++) {
        pr[i] = min(pr[i], pr[i - 1]);
    }
    for (int i = q - 2; i >= 0; i--) {
        sf[i] = min(sf[i], sf[i + 1]);
    }
    for (int i = 0; i + 1 < n; i++) {
        ll l = 0, r = x[i + 1] - x[i] + 1, d = x[i + 1] - x[i];
        if (abs(mn) + mx <= x[i + 1] - x[i]) {
            ans[i] += mx;
            ans[i + 1] += abs(mn);
            continue;
        }
        while (r - l > 1) {
            ll mid = (r + l) / 2;
            int j = lower_bound(u.begin(), u.end(), mid) - u.begin();
            int k = upper_bound(u.begin(), u.end(), -(d - mid + 1)) - u.begin() - 1;
            if (sf[j] < pr[k]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        ans[i] += l;
        ans[i + 1] += d - l;
    }
    ans[0] += abs(mn);
    ans.back() += abs(mx);
    for (int i = 0; i < n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 464 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Runtime error 6 ms 724 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 464 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Runtime error 6 ms 724 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -