Submission #381247

#	Time	Username	Problem	Language	Result	Execution time	Memory
381247		limabeans	Snowball (JOI21_ho_t2)	C++17	100 / 100	126 ms	14300 KiB

Main

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const ll inf = 1e18;

const int maxn = 2e5 + 10;



int n,q;


ll x[maxn];
ll ans[maxn];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q;

    for (int i=1; i<=n; i++) {
	cin>>x[i];
    }
    x[0]=-inf;
    x[n+1]=inf;

    vector<pair<ll,int>> t;
    for (int i=0; i<=n; i++) {
	t.push_back({x[i+1]-x[i],i});
    }


    sort(t.begin(), t.end());

    int idx = 0;
    ll L = 0;
    ll R = 0;
    ll at = 0;


    while (q--) {
	ll w;
	cin>>w;
	at += w;
	
	if (w>=0) {
	    R = max(R, at);
	    while (idx<=n && t[idx].first<L+R) {
		ans[t[idx].second+1] += L;
		ans[t[idx].second] += (t[idx].first-L);
		idx++;
	    }
	} else {
	    L = max(L, -at);
	    while (idx<=n && t[idx].first<L+R) {
		ans[t[idx].second] += R;
		ans[t[idx].second+1] += (t[idx].first-R);
		idx++;
	    }
	}
    }


    while (idx<=n) {
	ans[t[idx].second] += R;
	ans[t[idx].second+1] += L;
	idx++;
    }

    for (int i=1; i<=n; i++) {
	cout<<ans[i]<<"\n";
    }
    
    return 0;
}

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