Submission #760491

#	Time	Username	Problem	Language	Result	Execution time	Memory
760491		Boomyday	Snowball (JOI21_ho_t2)	C++17	100 / 100	274 ms	17684 KiB

Main

//
// Created by adavy on 2/12/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

using ost = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;


// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define trav(a,x) for (auto& a: x)


#define all(x) begin(x), end(x)
#define pb push_back


const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);



int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int N, Q;
    cin >> N >> Q;
    vl pos(N);
    F0R(i, N) cin >> pos[i];
    vl shf(Q);
    F0R(i, Q) cin >>shf[i];
    vl ans(N, 0);
    vl lb(Q+1, 0), ub(Q+1, 0);
    vi trn(Q+1, 0);
    vl cvrg(Q+1, 0);

    ll cur = 0;
    F0R(i, Q){
        cur += shf[i];
        if (shf[i] < 0){
            trn[i+1] = -1;
        } else trn[i+1] = 1;
        lb[i+1] = max(lb[i], cur);
        ub[i+1] = max(ub[i], -cur);
        cvrg[i+1] = lb[i+1]+ub[i+1];
    }
    ans[N-1] += lb[Q];
    ans[0] += ub[Q];




    F0R(i, N-1){
        ll dif = pos[i+1] - pos[i];
        int ind = lower_bound(all(cvrg), dif) - cvrg.begin();
        if (ind == Q+1) ind = Q;
        ll amt = cvrg[ind];
        ans[i] += lb[ind];
        ans[i+1] += ub[ind];
        if (amt > dif){
            if (trn[ind] == -1){ // go left, subtract right
                ans[i+1] -= amt - dif;
            }
            else ans[i] -= amt - dif;
        }

    }
    trav(i, ans) cout << i << endl;
}

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