Submission #1102520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102520		NotLinux	Snowball (JOI21_ho_t2)	C++17	0 / 100	2 ms	684 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int inf = 1e18 + 7;
void solve(){
	int n,q;
	cin >> n >> q;
	int arr[n];
	for(int i = 0;i<n;i++)cin >> arr[i];
	int query[q] , sum = 0 , premin[q] , premax[q];
	for(int i = 0;i<q;i++){
		cin >> query[i];
	}
	// cout << "arr : ";for(int i = 0;i<n;i++)cout << arr[i] << " ";cout << endl;
	// cout << "query : ";for(int i = 0;i<q;i++)cout << query[i] << " ";cout << endl;
	map < int , int > mpa;// first time reaching sum
	for(int i = 0;i<q;i++){
		sum += query[i];
		premin[i] = min(i == 0 ? 0 : premin[i-1] , sum);
		premax[i] = max(i == 0 ? 0 : premax[i-1] , sum);
		if(mpa.count(sum) == 0){
			mpa[sum] = i;
		}
	}
	// cout << "premax : ";for(int i = 0;i<q;i++)cout << premax[i] << " ";cout << endl;
	// cout << "premin : ";for(int i = 0;i<q;i++)cout << premin[i] << " ";cout << endl;
	int ans[n] = {0};
	ans[0] += abs(premin[q-1]);
	ans[n-1] += premax[q-1];
	for(int i = 0;i<n-1;i++){
		// cout << "		i : " << i << " , " << arr[i] << " " << arr[i+1] << endl;
		int l = 0 , r = q;
		while(l < r){
			int mid = (l + r) / 2;
			// cout << mid << " : " << arr[i] + premax[mid] << " , " << arr[i+1] + premin[mid] << endl;
			if((arr[i] + premax[mid]) >= (arr[i+1] + premin[mid]))r = mid;
			else l = mid+1;
		}
		// cout << "l : " << l << endl;
		if(l == q){// they dont collide
			// cout << "dont collide" << endl;
			ans[i] += premax[q-1];
			ans[i+1] += abs(premin[q-1]);
		}
		else{
			int point;// arr[i] moves till point , arr[i+1] moves till point+1
			// cout << "premax : " << premax[l] << " , premin : " << premin[l] << endl;
			if(mpa[premax[l]] < mpa[premin[l]]){
				// cout << "maxfirst" << endl;
				point = arr[i] + premax[l];
			}
			else{
				// cout << "minfirst" << endl;
				point = arr[i+1] + premin[l];
			}
			// cout << "point : " << point << endl;
			ans[i] += point - arr[i];
			ans[i+1] += arr[i+1] - point;
		}
	}
	for(int i = 0;i<n;i++){
		cout << ans[i] << '\n';
	}
	cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
/*	
 * dont get stuck on one approach , try different ones
 * if you think the implementation is long & messy , change your approach
 * think simple , dont overkill
 */

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