Submission #136669

#	Time	Username	Problem	Language	Result	Execution time	Memory
136669		choikiwon	MP3 Player (CEOI10_mp3player)	C++17	100 / 100	759 ms	15440 KiB

mp3player

#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 (stderr)

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 / 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