Submission #862156

#	Time	Username	Problem	Language	Result	Execution time	Memory
862156		vjudge1	Snowball (JOI21_ho_t2)	C++17	100 / 100	98 ms	15488 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 7;
const int N = 2e5 + 15;
const ll inf = 1e18;
int n, q;
ll X[N], W[N];
ll mn[N], mx[N];
ll ans[N];
int main(){
	scanf("%d%d", &n, &q);
	X[0] = -inf, X[n+1] = inf;
	for (int i=1;i<=n;i++){
		scanf("%lld", X+i);
	}
	ll prf=0;
	for (int i=1;i<=q;i++){
		scanf("%lld", W+i);
		prf += W[i];
		mn[i] = min(mn[i-1], prf);
		mx[i] = max(mx[i-1], prf);
	}
	ll D = -mn[q] + mx[q];
	ans[1] += -mn[q];
	ans[n] += mx[q];
	for (int i=1;i<=n-1;i++){
		ll dis = X[i+1]-X[i];
		if (dis >= D){
			ans[i] += mx[q];
			ans[i+1] += -mn[q];
			continue;
		}
		// the touch each other
		int L=0, R=q;
		while (R-L>1){
			int M = (L+R)>>1;
			if (mx[M] + -mn[M] >= dis){
				R = M;
			}
			else {
				L = M;
			}
		}
		if (mx[L]==mx[R]){// the min moved
			ans[i] += mx[L];
			ans[i+1] += dis-mx[L];
		}
		else {
			ans[i+1] += -mn[L];
			ans[i] += dis+mn[L];
		}
	}
	for (int i=1;i<=n;i++){
		printf("%lld\n", ans[i]);
	}
}

Compilation message (stderr)

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

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