提出 #70627629

---

ソースコード 拡げる

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<string>
#include<cmath>
#include<set>
#include<queue>

using namespace std;

int n;
set<int> s;
unordered_map<int, long long> mp;
long long ret = 0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	s.insert(0);
	mp[0] = 0;
	int num;
	cin >> num;
	s.insert(num);
	mp[0] = num;
	mp[num] = num;
	ret = num * 2;
	cout << ret << '\n';
	for (int i = 1; i < n; i++) {
		cin >> num;
		auto right = s.upper_bound(num);
		auto left = (right == s.begin() ? s.end() : prev(right));

		long long a = (left == s.end() ? 2000000000 : num - *left);
		long long b = (right == s.end() ? 2000000000 : *right - num);
		long long dist = min(a, b);
		
		if (left != s.end()) {
			ret -= mp[*left];
			mp[*left] = min(mp[*left], (long long)num - *left);
			ret += mp[*left];
		}
		if (right != s.end()) {
			ret -= mp[*right];
			mp[*right] = min(mp[*right], (long long)*right - num);
			ret += mp[*right];
		}
		mp[num] = dist;
		ret += dist;
		s.insert(num);

		cout << ret << '\n';
	}
}

提出情報

ジャッジ結果