제출 #711993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711993		tutis	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	242 ms	30292 KiB

bulves

/*input
6
1 2
0 0
2 0
0 0
0 0
0 1

*/
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<typename A, typename B>
using omap = tree <A, B, less<A>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename A>
using oset = tree <A, null_type, less<A>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;
ll ran(ll a, ll b)
{
	//return a + (ll)(rng() % (b - a + 1));
	return uniform_int_distribution<ll>(a, b)(rng);
}
ll power(ll x, ll p)
{
	if (abs(x) >= mod)
		x %= mod;
	if (x < 0)
		x += mod;
	if (abs(p) >= mod - 1)
		p %= mod - 1;
	if (p < 0)
		p += mod - 1;
	ll r = 1;
	while (p)
	{
		if (p % 2)
			r = (r * x) % mod;
		x = (x * x) % mod;
		p /= 2;
	}
	return r;
}
void solve()
{
	int N;
	cin >> N;
	int a[N];
	for (int i = 0; i < N; i++)
	{
		int f, b;
		cin >> f >> b;
		a[i] = f - b;
	}
	map<ll, ll>S;
	ll F = 1e6;
	ll pr = -5e11;
	S[pr] = -F;
	S[0] = F;
	ll v0 = F * -pr;
	ll sh = 0;
	ll sl = 0;
	for (int i = 0; i < N; i++)
	{
		sh += a[i];
		sl--;
		S[sh] += 2;
		auto it = --S.end();
		if (it->second == 1)
			S.erase(it);
		else
			it->second--;
		v0 += abs(pr - sh);
	}
	while ((--S.end())->first >= sh)
		S.erase(--S.end());
	S[sh] = 0;
	while (S.size() >= 2)
	{
		pair<ll, ll>x = *S.begin();
		sl += x.second;
		S.erase(S.begin());
		v0 += (S.begin()->first - x.first) * sl;
	}
	cout << v0 << "\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36