Submission #391476

# Submission time Handle Problem Language Result Execution time Memory
391476 2021-04-18T20:51:50 Z ritul_kr_singh Snowball (JOI21_ho_t2) C++17
0 / 100
1 ms 332 KB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, q; cin >> n >> q;
	int x[n]; for(int &i : x) cin >> i;
	int w[q]; for(int &i : w) cin >> i;

	for(int i=1; i<q; ++i) w[i] += w[i-1];

	int a[q], b[q];
	a[0] = max(w[0], 0LL);
	b[0] = min(w[0], 0LL);

	for(int i=1; i<q; ++i) a[i] = max(a[i-1], w[i]);
	for(int i=1; i<q; ++i) b[i] = min(b[i-1], w[i]);

	for(int &i : b) i = -i;

	int l[n], r[n];
	fill(l, l+n, 0LL);
	fill(r, r+n, 0LL);

	for(int i=0; i+1<n; ++i){
		int mx = 0, diff = x[i+1] - x[i];
		if(a[0] + b[0] >= diff){
			r[i] = min(diff, a[0]);
			l[i+1] = min(diff, b[0]);
			continue;
		}
		for(int y=q-1; y; y/=2)
			if(mx+y < q and a[mx+y] + b[mx+y] < diff) mx += y;
		r[i] = a[mx];
		l[i+1] = b[mx];
		++mx;
		if(mx < q){
			if(w[mx] < 0) l[i+1] = min(diff - a[mx-1], -w[mx]);
			else r[i] = min(diff - b[mx-1], w[mx]);
		}
	}
	l[0] = b[q-1];
	r[n-1] = a[q-1];
	for(int i=0; i<n; ++i) cout << l[i] + r[i] nl;
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -