제출 #1274773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274773		MisterReaper	Snowball (JOI21_ho_t2)	C++20	100 / 100	67 ms	11476 KiB

Main

// File snowball.cpp created on 30.09.2025 at 19:27:47
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, Q;
    std::cin >> N >> Q;

    std::vector<i64> X(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i];
    }

    std::vector<i64> W(Q + 1);
    for (int i = 1; i <= Q; ++i) {
        std::cin >> W[i];
    }

    for (int i = 1; i <= Q; ++i) {
        W[i] += W[i - 1];
    }

    std::vector<i64> minW(Q + 1), maxW(Q + 1), sum(Q + 1);
    for (int i = 1; i <= Q; ++i) {
        minW[i] = std::min(minW[i - 1], W[i]);
        maxW[i] = std::max(maxW[i - 1], W[i]);
        sum[i] = std::max(sum[i - 1], -minW[i] + maxW[i]);
    }

    std::vector<i64> ans(N);

    ans[0] += -minW[Q];
    ans[N - 1] += maxW[Q];

    for (int i = 0; i + 1 < N; ++i) {
        i64 d = X[i + 1] - X[i];
        if (d >= sum[Q]) {
            ans[i] += maxW[Q];
            ans[i + 1] += -minW[Q];
        } else {
            int j = int(std::lower_bound(sum.begin(), sum.end(), d) - sum.begin() - 1);
            ans[i] += maxW[j];
            ans[i + 1] += -minW[j];
            if (W[j + 1] > W[j]) {
                ans[i] += d - (maxW[j] - minW[j]);
            } else {
                ans[i + 1] += d - (maxW[j] - minW[j]);
            }
        }
    }

    for (int i = 0; i < N; ++i) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}

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