oj.uz

Submission #960930

# Submission time Handle Problem Language Result Execution time Memory
960930 2024-04-11T09:04:13 Z happy_node Snowball (JOI21_ho_t2) C++17
0 / 100
 1 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=2e5+5;

int N,Q;
ll X[MX],W[MX],ans[MX],L[MX],R[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>Q;
	for(int i=1;i<=N;i++) cin>>X[i];
	ll sum=0;
	for(int i=1;i<=Q;i++) {
		cin>>W[i];
		sum+=W[i];
		L[i]=min(L[i-1],sum);
		R[i]=max(R[i-1],sum);
	}

	for(int i=1;i<N;i++) {
		int l=0,r=Q,res=0;
		while(l<=r) {
			int m=(l+r)/2;
			if(R[m]-L[m]<X[i+1]-X[i]) {
				l=m+1,res=m;
 			} else {
 				r=m-1;
 			}
		}
		ans[i]+=R[res];
		ans[i+1]-=L[res];
		if(W[res+1]>0) 
			ans[i]+=(X[i+1]-X[i])-(R[res]-L[res]);
		else
			ans[i+1]+=(X[i+1]-X[i])-(R[res]-L[res]);
	}

	ans[1]-=L[Q];
	ans[N]+=R[Q];

	for(int i=1;i<=N;i++) cout<<ans[i]<<'\n';
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -