Submission #711996

#	Time	Username	Problem	Language	Result	Execution time	Memory
711996		tutis	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	209 ms	22544 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;
	}
	priority_queue<pair<ll, ll>>S;
	ll F = 1e6;
	ll pr = -5e11;
	S.push({pr, -F});
	S.push({0, F});
	ll v0 = F * -pr;
	ll sh = 0;
	ll sl = 0;
	for (int i = 0; i < N; i++)
	{
		sh += a[i];
		sl--;
		S.push({sh, 2});
		if (S.top().second == 1)
			S.pop();
		else
		{
			pair<ll, ll>x = S.top();
			S.pop();
			x.second--;
			S.push(x);
		}
		v0 += abs(pr - sh);
	}
	while (S.top().first >= sh)
		S.pop();
	S.push({sh, 0});
	vector<pair<ll, ll>>V;
	while (!S.empty())
	{
		V.push_back(S.top());
		S.pop();
	}
	reverse(V.begin(), V.end());
	for (int i = 0; i + 1 < V.size(); i++)
	{
		sl += V[i].second;
		v0 += (V[i + 1].first - V[i].first) * sl;
	}
	cout << v0 << "\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

Compilation message (stderr)

bulves.cpp: In function 'void solve()':
bulves.cpp:96:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for (int i = 0; i + 1 < V.size(); i++)
      |                  ~~~~~~^~~~~~~~~~

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