Submission #936847

#	Time	Username	Problem	Language	Result	Execution time	Memory
936847		jcelin	Snowball (JOI21_ho_t2)	C++14	100 / 100	132 ms	25652 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int off = 1 << logo;

ll L[MAXN], R[MAXN], arr[MAXN];
ll neg[MAXN], poz[MAXN], w[MAXN];

void solve(){
	int n, q;
	cin >> n >> q;
	for(int i=1; i<=n; i++) cin >> arr[i];
	ll cd = 0;
	for(int i=1; i<=q; i++){
		cin >> w[i];
		cd += w[i];
		neg[i] = min(neg[i - 1], cd);
		poz[i] = max(poz[i - 1], cd);
	}
	
	L[1] = arr[1] + neg[q];
	R[n] = arr[n] + poz[q];
	for(int i=1; i<n; i++){
		int lo = 1, hi = q, ret = -1;
		ll delt = arr[i + 1] - arr[i];
		while(lo <= hi){
			int mid = (lo + hi) / 2;
			if(poz[mid] + abs<ll>(neg[mid]) >= delt) ret = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		
		if(ret == -1){
			R[i] = arr[i] + poz[q];
			L[i + 1] = arr[i + 1] + neg[q];
		}else{
			R[i] = arr[i] + poz[ret - 1];
			L[i + 1] = arr[i + 1] + neg[ret - 1];
			
			if(w[ret] < 0) L[i + 1] = R[i];
			else R[i] = L[i + 1];
			
		}
	}
	
	for(int i=1; i<=n; i++) cout << R[i] - L[i] << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

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