oj.uz

Submission #690397

# Submission time Handle Problem Language Result Execution time Memory
690397 2023-01-30T07:12:11 Z valerikk Ants and Sugar (JOI22_sugar) C++17
0 / 100
 4000 ms 9720 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Execution timed out 4042 ms 9720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -