oj.uz

Submission #706161

# Submission time Handle Problem Language Result Execution time Memory
706161 2023-03-06T03:07:36 Z Pring Snowball (JOI21_ho_t2) C++14
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> pii;

struct P {
    int el, er;
    int val() {
        return el + er;
    }
};

const int MXN = 200005;

int n, q, a[MXN], w[MXN], wei[MXN], dil, bound;
P p[MXN];
vector<int> v;

void getP() {
    int now = 0;
    v.push_back(0);
    for (int i = 0; i < q; i++) {
        now += w[i];
        if (v.back() >= 0 && now > v.back()) v.pop_back();
        else if (v.back() <= 0 && now < v.back()) v.pop_back();
        v.push_back(now);
    }
    dil = v.size();
    P pp = {0, 0};
    for (int i = 0; i < dil; i++) {
        if (v[i] > 0) pp.el = v[i];
        else pp.er = -v[i];
        p[i] = pp;
    }
    bound = pp.val();
}

void solve(int id) {
    int space = a[id] - a[id - 1];
    P pp;
    if (space > bound) {
        pp = p[dil - 1];
    } else {
        auto it = upper_bound(p, p + dil, space, [](int a, P b) {
            return a < b.val();
        });
        P pb = *it;
        it--;
        P pa = *it;
        pp = pa;
        int x = space - pa.val();
        if (pa.el == pb.el) {
            pp.er += x;
        } else {
            pp.el += x;
        }
    }
    wei[id - 1] += pp.el;
    wei[id] += pp.er;
    // cout << pp.el << ' ' << pp.er << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> w[i];
    getP();
    // for (int i = 0; i < dil; i++) cout << v[i] << ' ';
    // cout << endl;
    for (int i = 1; i < n; i++) {
        solve(i);
    }
    wei[0] += p[dil - 1].er;
    wei[n - 1] += p[dil - 1].el;
    for (int i = 0; i < n; i++) cout << wei[i] << '\n';
    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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 1 ms 468 KB Output isn't correct
8 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 1 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -