제출 #1102536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102536		NotLinux	Snowball (JOI21_ho_t2)	C++17	100 / 100	261 ms	28248 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];
	}
	map < int , int > mpa;// first time reaching sum
	mpa[0] = -1;
	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;
		}
	}
	int ans[n] = {0};
	ans[0] += abs(premin[q-1]);
	ans[n-1] += premax[q-1];
	for(int i = 0;i<n-1;i++){
		int l = 0 , r = q;
		while(l < r){
			int mid = (l + r) / 2;
			if((arr[i] + premax[mid]) >= (arr[i+1] + premin[mid]))r = mid;
			else l = mid+1;
		}
		// cout << i << " : " << arr[i] << " " << arr[i+1] << endl;
		if(l == q){// they dont collide
			ans[i] += premax[q-1];
			ans[i+1] += abs(premin[q-1]);
			// cout << "didnt collide" << endl;
		}
		else{
			int point;// arr[i] moves till point , arr[i+1] moves till point+1
			if(mpa[premax[l]] < mpa[premin[l]]){
				point = arr[i] + premax[l];
			}
			else{
				point = arr[i+1] + premin[l];
			}
			// cout << "collide at : " << 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: 33 / 33
• Subtask 2: 67 / 67