oj.uz

Submission #136669

# Submission time Handle Problem Language Result Execution time Memory
136669 2019-07-26T05:56:16 Z choikiwon MP3 Player (CEOI10_mp3player) C++17
100 / 100
 759 ms 15440 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int maxn = 100010;

int N, Vmax, V2;
pii B[maxn];
vector<int> V[maxn];

int Xn;
vector<int> X;
unordered_map<int, int> dx;

struct BIT {
    vector<int> tree, lazy;
    void init() {
        tree = vector<int>(4 * N, 0);
        lazy = vector<int>(4 * N, 0);
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[2*n] += lazy[n];
            lazy[2*n] += lazy[n];
            tree[2*n + 1] += lazy[n];
            lazy[2*n + 1] += lazy[n];
            lazy[n] = 0;
        }
    }
    void upd(int a, int b, int d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] += d;
            lazy[n] += d;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, d, l, m, 2*n);
        upd(a, b, d, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return -1e9;
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit1, bit2;

int find0(int v) {
    int s = 0, e = N - 1, p = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        if(-bit2.quer(m, N - 1, 0, N - 1, 1) <= v) {
            p = m;
            s = m + 1;
        }
        else e = m - 1;
    }
    return p;
}
int find1(int v) {
    int s = 0, e = N - 1, p = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        if(bit1.quer(m, N - 1, 0, N - 1, 1) >= v) {
            p = m;
            s = m + 1;
        }
        else e = m - 1;
    }
    return p;
}

int main() {
    scanf("%d %d %d", &N, &Vmax, &V2);

    for(int i = 0; i < N; i++) {
        char t; int x; scanf("\n%c %d", &t, &x);
        B[i] = { t == '+', x };
    }

    for(int i = 1; i < N; i++) {
        X.push_back(B[i].second - B[i - 1].second);
    }

    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());
    Xn = X.size();
    for(int i = 0; i < Xn; i++) dx[X[i]] = i;

    for(int i = 1; i < N; i++) {
        V[ dx[ B[i].second - B[i - 1].second ] ].push_back(i);
    }

    bit1.init();
    bit2.init();
    bit1.upd(0, N - 1, V2, 0, N - 1, 1);
    bit2.upd(0, N - 1, -V2, 0, N - 1, 1);
    for(int i = N - 1; i >= 1; i--) {
        if(B[i].first) {
            bit1.upd(0, i - 1, -1, 0, N - 1, 1);
            bit2.upd(0, i - 1, 1, 0, N - 1, 1);
        }
        else {
            bit1.upd(0, i - 1, 1, 0, N - 1, 1);
            bit2.upd(0, i - 1, -1, 0, N - 1, 1);
        }
    }

    for(int x = Xn - 1; x >= -1; x--) {
        int t = find0(0);
        int d = find1(Vmax);

        if(t <= 0 && d <= 0) {
            if(x == Xn - 1) {
                printf("infinity");
                return 0;
            }
            printf("%d %d", X[x + 1] - 1, bit1.quer(0, 0, 0, N - 1, 1));
            return 0;
        }

        if(t < d) {
            int p = find1(Vmax + 1);

            if(p == -1 || p < t) {
                if(x == Xn - 1) {
                    printf("infinity");
                    return 0;
                }
                printf("%d %d", X[x + 1] - 1, Vmax);
                return 0;
            }
        }
        else {
            int p = find0(-1);

            if(p == -1) {
                if(x == Xn - 1) {
                    printf("infinity");
                    return 0;
                }
                printf("%d %d", X[x + 1] - 1, bit1.quer(0, 0, 0, N - 1, 1));
                return 0;
            }
            if(p < d) {
                if(x == Xn - 1) {
                    printf("infinity");
                    return 0;
                }
                printf("%d %d", X[x + 1] - 1, Vmax);
                return 0;
            }
        }

        if(x == -1) return 0;

        for(int i = 0; i < V[x].size(); i++) {
            int t = B[ V[x][i] ].first;

            if(t) {
                bit1.upd(0, V[x][i] - 1, 1, 0, N - 1, 1);
                bit2.upd(0, V[x][i] - 1, -1, 0, N - 1, 1);
            }
            else {
                bit1.upd(0, V[x][i] - 1, -1, 0, N - 1, 1);
                bit2.upd(0, V[x][i] - 1, 1, 0, N - 1, 1);
            }
        }
    }
}

Compilation message

mp3player.cpp: In function 'int main()':
mp3player.cpp:166:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < V[x].size(); i++) {
                        ~~^~~~~~~~~~~~~
mp3player.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &Vmax, &V2);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:86:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         char t; int x; scanf("\n%c %d", &t, &x);
                        ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3068 KB Output is correct
2 Correct 7 ms 2936 KB Output is correct
3 Correct 18 ms 3216 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2908 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Correct 10 ms 2936 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3192 KB Output is correct
2 Correct 23 ms 3344 KB Output is correct
3 Correct 21 ms 3192 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5548 KB Output is correct
2 Correct 164 ms 6136 KB Output is correct
3 Correct 167 ms 6240 KB Output is correct
4 Correct 145 ms 6008 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 5784 KB Output is correct
2 Correct 204 ms 6656 KB Output is correct
3 Correct 213 ms 6712 KB Output is correct
4 Correct 170 ms 6288 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 6392 KB Output is correct
2 Correct 39 ms 6652 KB Output is correct
3 Correct 305 ms 8484 KB Output is correct
4 Correct 217 ms 7080 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 8224 KB Output is correct
2 Correct 431 ms 9876 KB Output is correct
3 Correct 360 ms 9380 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 11376 KB Output is correct
2 Correct 759 ms 15408 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 12984 KB Output is correct
2 Correct 754 ms 15440 KB Output is correct