Submission #1143082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143082		nuutsnoynton	Snowball (JOI21_ho_t2)	C++20	100 / 100	250 ms	11452 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e5 + 2;
ll a[N], b[N], c[N];
int main() {
	ll n, m, r, x, y, s, i, j, p, ans, t, mx_lef, mx_rig, co;

	cin >> n >> m;
	
	for (i = 1; i <=n; i ++) {
		cin >> a[i];
	}
	vector < ll > v;
	vector < pair < ll, bool>  > is_lef;
	co = 0;
	mx_lef = mx_rig = 0;
	for (i = 1; i <= m; i ++) {
		cin >> b[i];
		if ( b[i] > 0) {
			co += b[i];
			if ( mx_rig >= co) continue;
			mx_rig = co;
			v.push_back(mx_lef + mx_rig);
			is_lef.push_back(make_pair(mx_lef, 1));
		}
		else {
			co += b[i];
			if ( mx_lef >= (-co)) continue;
			mx_lef = -co;
			v.push_back(mx_lef + mx_rig);
			is_lef.push_back(make_pair(mx_rig, 0));
		}
	}
	
	c[1] += mx_lef;
	c[n] += mx_rig;
	
	for (i = 1; i < n; i ++) {
		s = a[i + 1] - a[i];
		r = lower_bound(v.begin(), v.end(), s) - v.begin();
		if ( r == v.size()) {
			c[i] += mx_rig;
			c[i + 1] += mx_lef;
			continue;
		}
		if (is_lef[r].second == 1) {
			p = is_lef[r].first;
			p = min(p, s);
			c[i + 1] += p;
			c[i] += (s - p);
		}
		else {
			p = is_lef[r].first;
			p = min(p, s);
			c[i + 1] += (s - p);
			c[i] += p;
		}
//		cout << v[r] << " " << is_lef[r] << endl;
	}
	
	for (i = 1; i <= n; i ++) {
		cout << c[i] << endl;
	}
	
	
}

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