Submission #620816

#	Time	Username	Problem	Language	Result	Execution time	Memory
620816		patrikpavic2	Snowball (JOI21_ho_t2)	C++17	100 / 100	138 ms	15308 KiB

Main

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2e5 + 500;

typedef long long ll;

int n, q;
ll A[N], w[N];
ll dpL[N], dpR[N], ans[N];

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++)
		scanf("%lld", A + i);
	for(int i = 1;i <= q;i++)
		scanf("%lld", w + i);
	ll cur = 0;
	for(int i = 1;i <= q;i++){
		cur += w[i];
		dpL[i] = min(dpL[i - 1], cur);
		dpR[i] = max(dpR[i - 1], cur);
	}
	ans[0] -= dpL[q]; ans[n - 1] += dpR[q];
	for(int i = 0;i + 1 < n;i++){
		ll raz = A[i + 1] - A[i];
		int j = 0;
		for(int k = 17;k >= 0;k--){
			if(j + (1 << k) > q) continue;
			if(-dpL[j + (1 << k)] + dpR[j + (1 << k)] <= raz)
				j += (1 << k);
		}
		ans[i] += dpR[j];
		ans[i + 1] -= dpL[j];
		if(j < q){
			if(w[j + 1] > 0)
				ans[i] += raz + dpL[j] - dpR[j];
			else
				ans[i + 1] += raz + dpL[j] - dpR[j];
		}
	}
	for(int i = 0;i < n;i++)
		printf("%lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%lld", A + i);
      |   ~~~~~^~~~~~~~~~~~~~~
Main.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%lld", w + i);
      |   ~~~~~^~~~~~~~~~~~~~~

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