Submission #384006

#	Time	Username	Problem	Language	Result	Execution time	Memory
384006		danielcm585	Snowball (JOI21_ho_t2)	C++14	100 / 100	129 ms	11972 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<ll,int> ii;

const int N = 2e5;
const ll INF = 1e18;
int n, q;
ll x[N+2], ans[N+2];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    vector<ii> dl, dr;
    for (int i = 1; i <= n; i++) {
        if (i == 1) dl.push_back({INF,i});
        else dl.push_back({x[i]-x[i-1],i});
        if (i == n) dr.push_back({INF,i});
        else dr.push_back({x[i+1]-x[i],i});
    }
    sort(dl.begin(),dl.end());
    sort(dr.begin(),dr.end());
    ll pl = 0, pr = 0, lf = 0, rg = 0, ps = 0;
    while (q--) {
        ll w; cin >> w;
        ps += w;
        for (; pl < n && dl[pl].fi <= rg-ps; pl++) {
            ans[dl[pl].se] += max(-lf,dl[pl].fi-rg);
        }
        for (; pr < n && dr[pr].fi <= ps-lf; pr++) {
            ans[dr[pr].se] += max(rg,dr[pr].fi+lf);
        }
        lf = min(lf,ps);
        rg = max(rg,ps);
    }
    for (; pl < n; pl++) ans[dl[pl].se] += -lf;
    for (; pr < n; pr++) ans[dr[pr].se] += rg;
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

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