Submission #421177

#	Time	Username	Problem	Language	Result	Execution time	Memory
421177		dolphingarlic	MP3 Player (CEOI10_mp3player)	C++14	100 / 100	128 ms	11976 KiB

mp3player

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, vmax, v2, c[200001];

struct Node {
	int curr, mn, mx;

	Node operator+(Node B) {
		if (mx + curr <= B.mn) return {B.mn + B.curr - vmax, vmax, vmax};
		if (mn + curr >= B.mx) return {B.mx + B.curr - vmax, vmax, vmax};
		return {curr + B.curr, max(mn, B.mn - curr), min(mx, B.mx - curr)};
	}
} segtree[800001], lazy[800001];

char op[200001];
vector<int> comp;

void push_lazy(int node, int l, int r) {
	segtree[node] = segtree[node] + lazy[node];
	if (l != r) {
		lazy[node * 2] = lazy[node * 2] + lazy[node];
		lazy[node * 2 + 1] = lazy[node * 2 + 1] + lazy[node];
	}
	lazy[node] = {0, 0, vmax};
}

void update(int a, int b, int val, int node = 1, int l = 0,
			int r = comp.size() - 1) {
	push_lazy(node, l, r);
	if (l > b || r < a) return;
	if (l >= a && r <= b) {
		lazy[node] = {val, max(0, -val), vmax - max(0, val)};
		push_lazy(node, l, r);
	} else {
		int mid = (l + r) / 2;
		update(a, b, val, node * 2, l, mid);
		update(a, b, val, node * 2 + 1, mid + 1, r);
	}
}

Node query(int pos, int node = 1, int l = 0, int r = comp.size() - 1) {
	push_lazy(node, l, r);
	if (l == r) return segtree[node];
	int mid = (l + r) / 2;
	if (pos > mid) return query(pos, node * 2 + 1, mid + 1, r);
	return query(pos, node * 2, l, mid);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> vmax >> v2;
	for (int i = 0; i < n; i++) {
		cin >> op[i] >> c[i];
		if (i) comp.push_back(c[i] - c[i - 1]);
	}
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	Node base = {0, 0, vmax};
	fill_n(segtree + 1, 4 * n, base);
	fill_n(lazy + 1, 4 * n, base);

	for (int i = 1; i < n; i++) {
		int pos = lower_bound(comp.begin(), comp.end(), c[i] - c[i - 1]) -
				  comp.begin();
		int val = (op[i] == '+' ? 1 : -1);
		update(pos, comp.size() - 1, val);
	}
	for (int i = comp.size() - 1; ~i; i--) {
		Node res = query(i);
		int l = res.mn + res.curr, r = res.mx + res.curr;
		if (l <= v2 && v2 <= r) {
			if (i == comp.size() - 1)
				cout << "infinity";
			else {
				cout << comp[i + 1] - 1 << ' ';
				if (v2 == r)
					cout << vmax;
				else
					cout << v2 - res.curr;
			}
			return 0;
		}
	}
	cout << comp[0] - 1 << ' ' << v2;
	return 0;
}

Compilation message (stderr)

mp3player.cpp: In function 'int main()':
mp3player.cpp:74:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    if (i == comp.size() - 1)
      |        ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10