oj.uz

Submission #421177

# Submission time Handle Problem Language Result Execution time Memory
421177 2021-06-08T20:34:40 Z dolphingarlic MP3 Player (CEOI10_mp3player) C++14
100 / 100
 128 ms 11976 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 5 ms 716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 716 KB Output is correct
2 Correct 5 ms 716 KB Output is correct
3 Correct 5 ms 760 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2988 KB Output is correct
2 Correct 29 ms 2892 KB Output is correct
3 Correct 35 ms 2952 KB Output is correct
4 Correct 25 ms 2860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3324 KB Output is correct
2 Correct 34 ms 3328 KB Output is correct
3 Correct 30 ms 3276 KB Output is correct
4 Correct 28 ms 3020 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3892 KB Output is correct
2 Correct 34 ms 3880 KB Output is correct
3 Correct 60 ms 4432 KB Output is correct
4 Correct 33 ms 3592 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5520 KB Output is correct
2 Correct 60 ms 5632 KB Output is correct
3 Correct 51 ms 5200 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 11844 KB Output is correct
2 Correct 116 ms 11972 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 11908 KB Output is correct
2 Correct 95 ms 11976 KB Output is correct