Submission #988817

#	Time	Username	Problem	Language	Result	Execution time	Memory
988817		Ghetto	MP3 Player (CEOI10_mp3player)	C++17	40 / 100	89 ms	13376 KiB

mp3player

#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
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10