oj.uz

Submission #988817

# Submission time Handle Problem Language Result Execution time Memory
988817 2024-05-26T10:23:30 Z Ghetto MP3 Player (CEOI10_mp3player) C++17
40 / 100
 89 ms 13376 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5, INF = numeric_limits<int>::max();
 
int n, m, f;
int type[MAX_N];
map<int, vector<int>> moves;
 
struct Node { int min, max, lazy; };
Node st[4 * MAX_N];
void propogate(int u) {
    if (st[u].lazy == 0) return;
    st[2 * u].min += st[u].lazy, st[2 * u].max += st[u].lazy, st[2 * u].lazy += st[u].lazy;
    st[2 * u + 1].min += st[u].lazy, st[2 * u + 1].max += st[u].lazy, st[2 * u + 1].lazy += st[u].lazy;
    st[u].lazy = 0;
}
void update(int l, int r, int x, int u = 1, int lo = 1, int hi = n) {
    if (l <= lo && hi <= r) { st[u].min += x, st[u].max += x, st[u].lazy += x; return; }
    propogate(u);
    int mid = (lo + hi) / 2;
    if (l <= mid) update(l, r, x, 2 * u, lo, mid);
    if (r > mid) update(l, r, x, 2 * u + 1, mid + 1, hi);
    st[u].max = max(st[2 * u].max, st[2 * u + 1].max);
    st[u].min = min(st[2 * u].min, st[2 * u + 1].min);
}
int query(int i, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) return st[u].max;
    propogate(u);
    int mid = (lo + hi) / 2;
    if (i <= mid) return query(i, 2 * u, lo, mid);
    else return query(i, 2 * u + 1, mid + 1, hi);
}
int max_walk(int x, int u = 1, int lo = 1, int hi = n) { // First index (INF) with value >= x
    if (st[u].max < x) return INF;
    if (lo == hi) return lo;
    propogate(u);
    int mid = (lo + hi) / 2;
    if (st[2 * u].max >= x) return max_walk(x, 2 * u, lo, mid);
    else return max_walk(x, 2 * u + 1, mid + 1, hi);
}
int min_walk(int x, int u = 1, int lo = 1, int hi = n) {
    if (st[u].min > x) return INF;
    if (lo == hi) return lo;
    propogate(u);
    int mid = (lo + hi) / 2;
    if (st[2 * u].min <= x) return min_walk(x, 2 * u, lo, mid);
    else return min_walk(x, 2 * u + 1, mid + 1, hi);
}
 
int main() {
    // freopen("play.in", "r", stdin);
    cin >> n >> m >> f;
    int prev = 0;
    for (int i = 1; i <= n; i++) {
        char ch; cin >> ch;
        type[i] = (ch == '+') ? -1 : 1;
        int pos; cin >> pos;
        if (i != 1) moves[pos - prev].push_back(i);
        prev = pos;
    }
 
    update(1, n, f);
    int ans1 = moves.begin()->first - 1, ans2 = f;
    for (pair<int, vector<int>> x : moves) {
        for (int move : x.second) update(n - move + 2, n, type[move]);
        unordered_map<int, int> reach;
        reach[-1] = min_walk(-1), reach[0] = min_walk(0);
        reach[m] = max_walk(m), reach[m + 1] = max_walk(m + 1);
        // cout << x.first << ": " << reach[-1] << " " << reach[0] << " " << reach[m] << " " << reach[m + 1] << endl;
        bool is_lo_valid = (reach[m + 1] == INF || reach[0] < reach[m + 1]);
        bool is_hi_valid = (reach[-1] == INF || reach[m] < reach[-1]);
        if (!(is_lo_valid && is_hi_valid)) continue;
        ans1 = x.first;
        ans2 = (reach[m] == INF) ? query(n) : m;
    }
    if (ans1 == moves.rbegin()->first) cout << "infinity" << '\n';
    else cout << ans1 << " " << ans2 << '\n';
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3164 KB Output is correct
2 Correct 23 ms 5724 KB Output is correct
3 Correct 23 ms 5724 KB Output is correct
4 Correct 22 ms 5528 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 3672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7844 KB Output is correct
2 Correct 89 ms 13372 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 10288 KB Output is correct
2 Correct 79 ms 13376 KB Output is correct