oj.uz

Submission #396917

# Submission time Handle Problem Language Result Execution time Memory
396917 2021-05-01T01:30:47 Z AQT Snowball (JOI21_ho_t2) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;

int N, Q;
long long x[200005];
long long w[200005];
long long d[200005];
long long lft[200005], rht[200005];
long long ans[200005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	for(int i = 1; i <= N; i++){
		cin >> x[i];
	}
	for(int i = 1; i <= Q; i++){
		cin >> d[i];
		d[i] += d[i-1];
	}
	for(int i = 1; i <= Q; i++){
		if(d[i] < 0){
			rht[i] = -d[i];
		}
		else{
			lft[i] = d[i];
		}
		rht[i] = max(rht[i], rht[i-1]);
		lft[i] = max(lft[i], lft[i-1]);
	}
	ans[1] = rht[Q];
	ans[N] += lft[Q];
	for(int i = 1; i < N; i++){
		if(lft[Q] + rht[Q] > x[i + 1] - x[i]){
			int l = 1, r = N, k = 0;
			while(l <= r){
				int mid = (l + r)/2;
				if(lft[mid] + rht[mid] < x[i + 1] - x[i]){
					l = mid + 1;
				}
				else{
					r = mid - 1;
					k = mid;
				}
			}
			ans[i] += lft[k-1];
			ans[i+1] += rht[k-1];
			if(lft[k-1] != lft[k]){
				ans[i] += x[i + 1] - x[i] - lft[k-1] - rht[k-1];
			}
			else{
				ans[i+1] += x[i+1] - x[i] - lft[k-1] - rht[k-1];
			}
		}
		else{
			ans[i] += lft[Q];
			ans[i+1] += rht[Q];
		}
	}
	for(int i = 1; i <= N; i++){
		cout << ans[i] << "\n";
	}
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -