Submission #629943

#	Time	Username	Problem	Language	Result	Execution time	Memory
629943		QwertyPi	Snowball (JOI21_ho_t2)	C++14	100 / 100	236 ms	15516 KiB

Main

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

int x[200002];
int ans[200002];
struct Data{
	int tot, l, r;
	Data() = default;
	Data(int _t, int _l, int _r) : tot(_t), l(_l), r(_r){};
	bool operator< (const Data& o) const{
		return tot < o.tot;
	}
	
	void print(){
		cout << tot << ' ' << l << ' ' << r << endl;
	}
};

int32_t main(){
	int n, q;
	cin >> n >> q;
	x[0] = -(1LL << 60);
	for(int i = 1; i <= n; i++){
		cin >> x[i];
	}
	x[n + 1] = 1LL << 60;
	vector<Data> v {{0, 0, 0}};
	int l = 0, r = 0, x0 = 0;
	for(int i = 0; i < q; i++){
		int w; cin >> w;
		x0 += w;
		l = min(l, x0);
		r = max(r, x0);
		v.push_back({r - l, l, r});
	}
	for(int i = 0; i <= n; i++){
		auto ptr = upper_bound(v.begin(), v.end(), Data{x[i + 1] - x[i], 0, 0});
		Data d;
		if(ptr == v.end()){
			d = *prev(ptr);
		}else{
			Data d1 = *prev(ptr), d2 = *ptr;
			int dx = d2.l != d1.l, dy = d2.r != d1.r;
			d = {x[i + 1] - x[i], d1.l - dx * (x[i + 1] - x[i] - d1.tot), d1.r + dy * (x[i + 1] - x[i] - d1.tot)};
		}
		ans[i] += d.r, ans[i + 1] += -d.l;
	}
	for(int i = 1; i <= n; i++){
		cout << ans[i] << ' '; 
	}
	cout << endl; 
}

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