Submission #690397

#	Time	Username	Problem	Language	Result	Execution time	Memory
690397		valerikk	Ants and Sugar (JOI22_sugar)	C++17	0 / 100	4042 ms	9720 KiB

sugar

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 7;
const ll INF = 2e18;

int q, L;
struct query {
	int t, x;
	ll a;
} qr[N];
int n;
vector<int> xs;
ll a[N], b[N];

void adda(int l, int r, ll d) {
	for (int i = l; i < r; ++i) {
		a[i] += d;
	}
}

void addb(int l, int r, ll d) {
	for (int i = l; i < r; ++i) {
		b[i] += d;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> q >> L;
	for (int i = 0; i < q; ++i) {
		cin >> qr[i].t >> qr[i].x >> qr[i].a;
		if (qr[i].t == 1) {
			xs.push_back(qr[i].x);
		}
	}
	sort(xs.begin(), xs.end());
	xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
	n = xs.size();
	// max (kekr[j] - kekl[i]) - (lolr[j] - loll[i])
	// kekr[j] = ants <= x[j]
	// kekl[i] = ants < x[i]
	// lolr[j] = sugar <= x[j] + L
	// loll[i] = sugar < x[i] - L

	// a[i] = loll[i] - kekl[i]
	// b[j] = kekr[j] - lolr[j]
	// max a[i] + b[j] (i <= j)
	ll tot = 0;		
	for (int i = 0; i < q; ++i) {
		if (qr[i].t == 1) {
			tot += qr[i].a;
			adda(upper_bound(xs.begin(), xs.end(), qr[i].x) - xs.begin(), n, -qr[i].a);
			addb(lower_bound(xs.begin(), xs.end(), qr[i].x) - xs.begin(), n, qr[i].a);
		} else {
			adda(upper_bound(xs.begin(), xs.end(), qr[i].x + L) - xs.begin(), n, qr[i].a);
			addb(lower_bound(xs.begin(), xs.end(), qr[i].x - L) - xs.begin(), n, -qr[i].a);
		}
		ll mx = 0, mxa = -INF;
		for (int j = 0; j < n; ++j) {
			mxa = max(mxa, a[j]);
			mx = max(mx, mxa + b[j]);
		}
		cout << tot - mx << "\n";
	}
	return 0;
}

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