oj.uz

Submission #936910

# Submission time Handle Problem Language Result Execution time Memory
936910 2024-03-03T02:36:47 Z the_coding_pooh Snowball (JOI21_ho_t2) C++14
0 / 100
 1 ms 348 KB 
#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), -mnL + 1LL);
        W[i + 1] += min(max(L, X[i + 1] - X[i] - R), mxR + 1LL);
        //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
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -