Submission #1261595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261595		4QT0R	Two Currencies (JOI23_currencies)	C++20	30 / 100	727 ms	9276 KiB

currencies

/*
Podzadanie: Ścieżka

Zamiast drzewa przedziałowego na pre-orderach, drzewo przedziałowe symulujące sumy prefiksowe.
*/

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const int II = 1'000'000'000;
const ll I = 1'000'000'000'000'000'000LL;
const int K = 17;
const int N = 1 << K;

ll drz[2 * N];

pair<ll, ll> il[N];
int v1[N], v2[N];
int poc[N], kon[N];
ll akt[N];
pair<int, int> que[N];

pair<int, int> dod[N];

ll answer[N];

void Add(int a, int b, ll x)
{
	a += N - 1;
	b += N + 1;
	while (a / 2 != b / 2)
	{
		if (a % 2 == 0)
			drz[a + 1] += x;
		if (b % 2 == 1)
			drz[b - 1] += x;
		a /= 2;
		b /= 2;
	}
}

ll Sum(int v)
{
	ll ans = 0LL;
	v += N;
	while (v > 0)
	{
		ans += drz[v];
		v /= 2;
	}
	return ans;
}

void Check(int m, int q, bool r)
{
	for (int i = 1; i < 2 * N; ++i)
		drz[i] = 0;
	int j = 0;
	sort(que + 1, que + 1 + q);
	for (int i = 1; i <= q; ++i)
	{
		while (j < m && dod[j + 1].st <= que[i].st)
		{
			++j;
			if (r)
				Add(dod[j].nd, N, dod[j].st);
			else
				Add(dod[j].nd, N, 1);
		}
		int a = que[i].nd;
		ll cur = Sum(v2[a]) - Sum(v1[a]);
		akt[a] = cur;
	}
}

void BS(int m, int q)
{
	for (int i = 1; i <= q; ++i)
	{
		poc[i] = 0;
		kon[i] = II;
	}
	for (int xd = 1; xd <= 30; ++xd)
	{
		for (int i = 1; i <= q; ++i)
			que[i] = pair{(poc[i] + kon[i] + 1) / 2, i};
		Check(m, q, 1);
		for (int i = 1; i <= q; ++i)
		{
			int s = (poc[i] + kon[i] + 1) / 2;
			if (akt[i] > il[i].nd)
				kon[i] = s - 1;
			else
				poc[i] = s;
		}
	}
}

void DoAns(int m, int q)
{
	for (int i = 1; i <= q; ++i)
		que[i] = pair{poc[i], i};
	Check(m, q, 1);
	for (int i = 1; i <= q; ++i)
		answer[i] = (il[i].nd - akt[i]) / (ll)(poc[i] + 1);
	Check(m, q, 0);
	for (int i = 1; i <= q; ++i)
	{
		answer[i] += akt[i];
		que[i] = pair{II + 1, i};
	}
	Check(m, q, 0);
	for (int i = 1; i <= q; ++i)
	{
		answer[i] = il[i].st - max(0LL, akt[i] - answer[i]);
		if (answer[i] < 0LL)
			answer[i] = -1LL;
	}
}

void Solve()
{
	int n, m, q, a, b;
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i)
	{
		cin >> a >> b;
	}
	for (int i = 1; i <= m; ++i)
	{
		cin >> a >> b;
		dod[i] = pair{b, a + 1};
	}
	sort(dod + 1, dod + 1 + m);
	for (int i = 1; i <= q; ++i)
	{
		cin >> v1[i] >> v2[i] >> il[i].st >> il[i].nd;
		if (v1[i] > v2[i])
			swap(v1[i], v2[i]);
	}
	BS(m, q);
	DoAns(m, q);
	for (int i = 1; i <= q; ++i)
		cout << answer[i] << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solve();

	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 30 / 30
• Subtask 4: 0 / 32