Submission #535385

#	Time	Username	Problem	Language	Result	Execution time	Memory
535385		PikaQ	Snowball (JOI21_ho_t2)	C++17	0 / 100	1 ms	468 KiB

Main

#include<bits/stdc++.h>
#define forn(i,n) for(int i = 0;i < (n);i++)
#define Forn(i,n) for(int i = 1;i <= (n);i++)
#define all(p) p.begin(),p.end()
#define pb push_back
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define debug(x) cout << #x << ' ' << x << '\n';
using namespace std;
const int INF = (int) 1e18 + 9;
int n,q;

void solve(){
	cin >> n >> q;
	vi x(n+1);
	vi w(q);
	Forn(i,n) cin >> x[i];
	forn(i,q) cin >> w[i];
	vi lt(n+1),rt(n+1),ans(n+1);
	Forn(i,n) lt[i] = q-1;
	Forn(i,n) rt[i] = q-1;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	Forn(i,n){
		if(i == 1) {
			pq.push({INF,-1});
		}else {
			pq.push({x[i] - x[i-1],-i});
		}
	}
	Forn(i,n){
		if(i == n){
			pq.push({INF,1});
		}else{
			pq.push({x[i+1] - x[i],i});
		}
	}
	int mx = 0,mn = 0,cur = 0;
	forn(i,q){
		cur += w[i];
		if(cur > mx){
			w[i] = cur - mx;
			mx = cur;
		}
		else if(cur < mn){
			w[i] = cur - mn;
			mn = cur;
		}
		else {
			w[i] = 0;
		}
	}
	//forn(i,q) debug(w[i]);
	int nn = 0,nm = 0;
	forn(i,q){
		if(w[i] > 0) nm += w[i];
		if(w[i] < 0) nn -= w[i];
		while(pq.top().F <= (nn + nm)){
			pii cur = pq.top();pq.pop();
			if(cur.S > 0){
				rt[cur.S] = i;
				if(w[i] > 0 && cur.F < (nn + nm)) ans[cur.S] -= (nn + nm) - cur.F;
				//debug(rt[cur.S]);
				//debug(cur.S);
			}else{
				cur.S *= -1;
				lt[cur.S] = i;
				if(w[i] < 0 && cur.F < (nn + nm)) ans[cur.S] -= (nn + nm) - cur.F;
			//	debug(lt[cur.S]);
			//	debug(cur.S);
			}
		}
	}
	vi sp(n),sn(n);
	forn(i,q){
		if(w[i] > 0) sp[i] += w[i];
		if(w[i] < 0) sn[i] -= w[i];
		if(i){
			sp[i] += sp[i-1];
			sn[i] += sn[i-1];
		}
	}
	Forn(i,n){
		ans[i] += sp[rt[i]];
		ans[i] += sn[lt[i]];
	}
	Forn(i,n) cout << ans[i] << ' ';
	cout << '\n';
}

signed main(){
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

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