Submission #712001

#	Time	Username	Problem	Language	Result	Execution time	Memory
712001		tutis	Potatoes and fertilizers (LMIO19_bulves)	C++17	30 / 100	106 ms	10572 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;
}
struct por
{
	ll x;
	int y;
	por(ll x, int y): x(x), y(y)
	{

	}
};
bool operator<(const por &a, const por &b)
{
	return a.x < b.x;
}
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;
	}
	for (int i = 1; i < N; i++)
		a[i] += a[i - 1];
	ll res = 0;
	for (int i = 0; i + 1 < N; i++)
	{
		if (a[i] < 0)
		{
			res += -a[i];
			a[i] = 0;
		}
		if (a[i] > a[N - 1])
		{
			res += a[i] - a[N - 1];
			a[i] = a[N - 1];
		}
	}
	priority_queue<por>S;
	S.push(por(0, 0));
	ll v0 = 0;
	ll sh = 0;
	ll sl = 0;
	for (int i = 0; i < N; i++)
	{
		sh = a[i];
		sl--;
		S.push(por(sh, 2));
		if (S.top().y == 1)
			S.pop();
		else
		{
			((por*)&S.top())->y--;
		}
		v0 += sh;
	}
	while (!S.empty() && S.top().x >= sh)
		S.pop();
	S.push(por(sh, 0));
	vector<por>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].y;
		v0 += (V[i + 1].x - V[i].x) * sl;
	}
	cout << v0 + res << "\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:119:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<por, std::allocator<por> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for (int i = 0; i + 1 < V.size(); i++)
      |                  ~~~~~~^~~~~~~~~~

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