Submission #936911

#	Time	Username	Problem	Language	Result	Execution time	Memory
936911		the_coding_pooh	Snowball (JOI21_ho_t2)	C++14	33 / 100	104 ms	12924 KiB

Main

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 2e3 + 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';
    }
}

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