Submission #135469

#	Time	Username	Problem	Language	Result	Execution time	Memory
135469		imeimi2000	MP3 Player (CEOI10_mp3player)	C++17	100 / 100	105 ms	4484 KiB

mp3player

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int n, Vmax, V2;
struct node {
    int L, R, A;
    node() : L(0), R(Vmax), A(0) {}
    void add(int v) {
        A += v;
        L += v;
        R += v;
        if (L > Vmax) --L;
        if (R > Vmax) --R;
        if (L < 0) ++L;
        if (R < 0) ++R;
    }
    void add(node &c) const {
        c.L += A;
        c.R += A;
        c.A += A;
        c.L = min(max(c.L, L), R);
        c.R = min(max(c.R, L), R);
    }
} seg[1 << 18];

void init(int i, int s, int e) {
    seg[i] = node();
    if (s == e) return;
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
}

char T[100001];
int C[100001];
vector<int> cp;

int find(int x) {
    return upper_bound(cp.begin(), cp.end(), x) - cp.begin();
}

void update(int i, int s, int e, int x, int v) {
    if (e < x) return;
    if (x <= s) {
        seg[i].add(v);
        return;
    }
    seg[i].add(seg[i << 1]);
    seg[i].add(seg[i << 1 | 1]);
    seg[i] = node();
    int m = (s + e) / 2;
    update(i << 1, s, m, x, v);
    update(i << 1 | 1, m + 1, e, x, v);
}

pii get_ans(int i, int s, int e) {
    if (s == e) {
        if (seg[i].L <= V2 && V2 <= seg[i].R) {
            if (V2 == seg[i].R) return pii(s, Vmax);
            return pii(s, V2 - seg[i].A);
        }
        else return pii(1, V2);
    }
    seg[i].add(seg[i << 1]);
    seg[i].add(seg[i << 1 | 1]);
    seg[i] = node();
    int m = (s + e) / 2;
    return max(get_ans(i << 1, s, m), get_ans(i << 1 | 1, m + 1, e));
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> Vmax >> V2;
    for (int i = 1; i <= n; ++i) {
        char in[10];
        cin >> in >> C[i];
        T[i] = in[0];
        if (i > 1) cp.push_back(C[i] - C[i - 1]);
    }
    cp.push_back(0);
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    int m = cp.size();
    init(1, 1, m);
    for (int i = 2; i <= n; ++i) {
        int t = find(C[i] - C[i - 1]);
        update(1, 1, m, t, T[i] == '+' ? 1 : -1);
    }
    pii ans = get_ans(1, 1, m);
    if (ans.first == m) printf("infinity\n");
    else printf("%d %d\n", cp[ans.first] - 1, ans.second);
    return 0;
}

• 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