Submission #531543

#	Time	Username	Problem	Language	Result	Execution time	Memory
531543		amunduzbaev	Snowball (JOI21_ho_t2)	C++17	100 / 100	120 ms	16912 KiB

Main

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

#define ar array
#define int long long

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	vector<int> x(n), p(q), is(q);
	for(int i=0;i<n;i++) cin>>x[i];
	for(int i=0;i<q;i++){
		cin>>p[i];
		is[i] = (p[i] > 0);
		if(i) p[i] += p[i-1];
	}
	
	vector<int> mn(q, 0), mx(q, 0);
	for(int i=0;i<q;i++){ 
		if(i) mn[i] = mn[i-1], mx[i] = mx[i-1];
		mn[i] = min(mn[i], p[i]);
		mx[i] = max(mx[i], p[i]);
	}
	
	vector<int> res(n);
	for(int i=1;i<n;i++){
		int l = 0, r = q;
		auto check = [&](int t){
			return (x[i-1] + mx[t] <= x[i] + mn[t]);
		};
		while(l < r){
			int m = (l + r) >> 1;
			if(check(m)) l = m + 1;
			else r = m;
		}
		
		if(l < q){
			int p;
			if(is[l]) p = x[i] + (l ? mn[l-1] : 0);
			else p = x[i-1] + (l ? mx[l-1] : 0);
			res[i-1] += (p - x[i-1]);
			res[i] += (x[i] - p);
		} else {
			res[i-1] += mx[q-1], res[i] += abs(mn[q-1]);
		}
	}
	//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
	//~ cout<<"\n";
	res[0] += abs(mn[q-1]), res[n-1] += mx[q-1];
	//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
	//~ cout<<"\n";
	for(int i=0;i<n;i++) cout<<res[i]<<"\n";
}

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