oj.uz

Submission #135469

# Submission time Handle Problem Language Result Execution time Memory
135469 2019-07-24T06:06:12 Z imeimi2000 MP3 Player (CEOI10_mp3player) C++17
100 / 100
 105 ms 4484 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 6 ms 3452 KB Output is correct
3 Correct 5 ms 3428 KB Output is correct
4 Correct 5 ms 3448 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3448 KB Output is correct
2 Correct 7 ms 3576 KB Output is correct
3 Correct 7 ms 3448 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3704 KB Output is correct
2 Correct 17 ms 4088 KB Output is correct
3 Correct 17 ms 3960 KB Output is correct
4 Correct 17 ms 3960 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3704 KB Output is correct
2 Correct 19 ms 3832 KB Output is correct
3 Correct 18 ms 3832 KB Output is correct
4 Correct 19 ms 3832 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3832 KB Output is correct
2 Correct 29 ms 4088 KB Output is correct
3 Correct 25 ms 4348 KB Output is correct
4 Correct 17 ms 4092 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3960 KB Output is correct
2 Correct 33 ms 3960 KB Output is correct
3 Correct 31 ms 4472 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 4472 KB Output is correct
2 Correct 67 ms 4472 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 4484 KB Output is correct
2 Correct 70 ms 4472 KB Output is correct