Submission #558562

#	Time	Username	Problem	Language	Result	Execution time	Memory
558562		savacska	Ants and Sugar (JOI22_sugar)	C++17	6 / 100	4091 ms	27376 KiB

sugar

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXQ = 500000;

pair <int, pair <int, int> > zapr[MAXQ + 5];
map <int, int> opa;
int inv[MAXQ + 5];
ll ants[MAXQ + 5], sugar[MAXQ + 5], cop[MAXQ + 5];

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	
 	int quer, len;
 	cin >> quer >> len;

 	for (int i = 1; i <= quer; i++)
 	{
 	 	int typ, x, cnt;
 	 	cin >> typ >> x >> cnt;

 	 	zapr[i] = mp(typ, mp(x, cnt));
 	 	opa.insert(mp(x, 0));
 	}

 	int cnt = 0;
 	for (auto it = opa.begin(); it != opa.end(); it++)
 	{
 		cnt++;
 		inv[cnt] = it->x;
 		it->y = cnt; 	
 	}

 	for (int i = 1; i <= quer; i++) zapr[i].y.x = opa[zapr[i].y.x];

 	for (int i = 1; i <= quer; i++)
 	{
 	 	if (zapr[i].x == 1) ants[zapr[i].y.x] += zapr[i].y.y;
 	 	else sugar[zapr[i].y.x] += zapr[i].y.y;

 	 	for (int k = 1; k <= cnt; k++) cop[k] = ants[k];
 	 	
 	 	int uk = 1;
 	 	ll ans = 0;
 	 	for (int k = 1; k <= cnt; k++)
 	 	{
 	 	 	if (sugar[k] == 0) continue;
 	 	 	while (uk <= cnt && (inv[k] - inv[uk] > len || cop[uk] == 0)) uk++;
 	 	 	
 	 	 	ll ost = sugar[k];
 	 	 	while (uk <= cnt && ost > 0 && (inv[uk] - inv[k]) <= len)
 	 	 	{
 	 	 		ll tt = min(ost, cop[uk]);
 	 	 		ost -= tt;
 	 	 		cop[uk] -= tt;
 	 	 		ans += tt;
 	 	 		if (cop[uk] == 0) uk++;
 	 	   	}
 	 	}

 	 	cout << ans << '\n';
 	}
 	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52