Submission #397678

#	Time	Username	Problem	Language	Result	Execution time	Memory
397678		ChrisT	Snowball (JOI21_ho_t2)	C++17	100 / 100	155 ms	15300 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e6 + 5;
int main () {
	int n,q; scanf ("%d %d",&n,&q);
	vector<long long> x(n), go(q);
	for (int i = 0; i < n; i++) scanf ("%lld",&x[i]);
	for (int i = 0; i < q; i++) scanf ("%lld",&go[i]);
	vector<long long> left(q), right(q);
	long long pre = 0;
	for (int i = 0; i < q; i++) {
		pre += go[i];
		left[i] = min(pre,i?left[i-1]:0LL);
		right[i] = max(pre,i?right[i-1]:0LL);
	}
	vector<long long> ret(n);
	for (int i = 1; i < n; i++) {
		int low = 0, high = q-1, mid, ans = -1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (x[i-1] + right[mid] >= x[i] + left[mid]) high = (ans = mid) - 1;
			else low = mid + 1;
		}
		if (ans == -1) ret[i-1] += right[q-1], ret[i] -= left[q-1];
		else if (go[ans] > 0) {
			long long cut = x[i] + left[ans];
			ret[i] += x[i] - cut;
			ret[i-1] += cut - x[i-1];
		} else {
			long long cut = x[i-1] + right[ans];
			ret[i-1] += cut - x[i-1];
			ret[i] += x[i] - cut;
		}
	}
	ret[0] -= left[q-1]; ret[n-1] += right[q-1];
	for (int i = 0; i < n; i++) printf ("%lld\n",ret[i]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:5:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    5 |  int n,q; scanf ("%d %d",&n,&q);
      |           ~~~~~~^~~~~~~~~~~~~~~
Main.cpp:7:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |  for (int i = 0; i < n; i++) scanf ("%lld",&x[i]);
      |                              ~~~~~~^~~~~~~~~~~~~~
Main.cpp:8:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |  for (int i = 0; i < q; i++) scanf ("%lld",&go[i]);
      |                              ~~~~~~^~~~~~~~~~~~~~~

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