제출 #936912

#제출 시각아이디문제언어결과실행 시간메모리
936912the_coding_poohSnowball (JOI21_ho_t2)C++14
100 / 100
287 ms24144 KiB
#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 2e5 + 5;

int N, Q;

const long long INF = 3e18 + 5;

long long L[SIZE], R[SIZE], W[SIZE], X[SIZE];

#define fs first
#define sc second

int main(){
    cin >> N >> Q;
    X[N + 1] = INF;
    X[0] = -INF;
    for (int i = 1; i <= N;i++){
        cin >> X[i];
        W[i] = 0;
    }

    long long in_W, mnL = 0, mxR = 0, nX = 0;

    multiset <pair<long long, long long>> opW;
    opW.insert({0, 0});
    for (int i = 1; i <= Q;i++){
        cin >> in_W;
        nX += in_W;
        mnL = min(nX, mnL);
        mxR = max(nX, mxR);
        opW.insert({mxR - mnL, mxR});
    }
    /*
    for(auto i:opW){
        cout << i.fs << ' ' << i.sc << '\n';
    }
    */
    pair<long long, long long> tmp, pretmp;
    W[1] += -mnL;
    W[N] += mxR;
    long long L, R;
    for (int i = 1; i < N;i++){
        tmp = *opW.lower_bound({X[i + 1] - X[i], 0LL});
        pretmp = *prev(opW.lower_bound({X[i + 1] - X[i], 0LL}));
        if(opW.lower_bound({X[i + 1] - X[i], 0LL}) == opW.end()){
            tmp = {mxR - mnL, mxR};
        }
        L = pretmp.fs - pretmp.sc;
        R = tmp.sc;
        W[i] += min(min(R, X[i + 1] - X[i] - L), mxR);
        W[i + 1] += min(max(L, X[i + 1] - X[i] - R), -mnL);
        //cout << W[i] << ' ' << W[i + 1] << ' ' << min(R, X[i + 1] - X[i] - L) << '\n';
    }

    for (int i = 1; i <= N;i++){
        cout << W[i] << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...