Submission #1092276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092276		ortsac	Snowball (JOI21_ho_t2)	C++17	100 / 100	185 ms	13752 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;

#define int long long


int INF = 0x3f3f3f3f3f3f3f3f;
vector<int> mx, mi;

bool check(int a, int b, int q) {
    int la = (a + mi[q]), ra = (a + mx[q]);
    int lb = (b + mi[q]), rb = (b + mx[q]);
    if ((la <= lb) && (lb <= ra)) return 1;
    if ((lb <= la) && (la <= rb)) return 1;
    return 0;
}

int32_t main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    int curr = 0;
    mx.resize(q + 1);
    mi.resize(q + 1);
    vector<int> x(q + 1);
    for (int i = 1; i <= q; i++) {
        cin >> x[i];
        curr += x[i];
        mx[i] = max(mx[i - 1], curr);
        mi[i] = min(mi[i - 1], curr);
    }
    for (int i = 1; i <= n; i++) {
        int left = q + 1, right = q + 1;
        if (i > 1) {
            int l = 0, r = q, ans = q + 1;
            while (l <= r) {
                int m = (l+r)/2;
                if (check(v[i - 1], v[i], m)) {
                    ans = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            left = ans;
        }
        if (i < n) {
            int l = 0, r = q, ans = q + 1;
            while (l <= r) {
                int m = (l+r)/2;
                if (check(v[i], v[i + 1], m)) {
                    ans = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            right = ans;
        }
        int amntl, amntr;
        // calc amntl
        if (left == (q + 1)) {
            amntl = abs(mi[q]);
        } else {
            if (x[left] > 0) {
                amntl = abs(mi[left - 1]);
            } else {
                amntl = abs(v[i] - (v[i - 1] + mx[left - 1]));
            }
        }
        // calc amntr
        if (right == (q + 1)) {
            amntr = abs(mx[q]);
        } else {
            if (x[right] < 0) {
                amntr = abs(mx[right - 1]);
            } else {
                amntr = abs((v[i + 1] + mi[right - 1]) - v[i]);
            }
        }
        // cout
        int amnt = 0;
        amnt += amntl;
        amnt += amntr;
        //cout << amntl << " " << amntr << "\n";
        cout << amnt << "\n";
    }
}

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