Submission #396926

#	Time	Username	Problem	Language	Result	Execution time	Memory
396926		AQT	Snowball (JOI21_ho_t2)	C++14	100 / 100	141 ms	15300 KiB

Main

#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];
	sort(x+1, x+1+N);
	for(int i = 1; i < N; i++){
		if(lft[Q] + rht[Q] > x[i + 1] - x[i]){
			int l = 1, r = Q, 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];
		if(i != N){
			cout << "\n";
		}
	}
}

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