oj.uz

Submission #585705

# Submission time Handle Problem Language Result Execution time Memory
585705 2022-06-29T08:48:21 Z 박상훈(#8384) MP3 Player (CEOI10_mp3player) C++17
100 / 100
 90 ms 8880 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int INF = 2e9+400;
bool p[100100], on[100100];
int a[100100], n, vmax, v2;

struct Node{
    int mn, imn, mx, imx;
    Node(){}
    Node(int _mn, int _imn, int _mx, int _imx): mn(_mn), imn(_imn), mx(_mx), imx(_imx) {}
    Node operator + (const Node &N) const{
        Node ret = *this;
        if (N.mn < ret.mn) ret.mn = N.mn, ret.imn = N.imn;
        if (N.mx > ret.mx) ret.mx = N.mx, ret.imx = N.imx;
        return ret;
    }
};

struct Seg{
    Node tree[400400], O;
    int lazy[400400];
    void init(int i, int l, int r, vector<int> &X){
        lazy[i] = 0;
        O = Node(1e9, -1, -1e9, -1);

        if (l==r) {tree[i] = Node(X[l], l, X[l], l); return;}
        int m = (l+r)>>1;
        init(i<<1, l, m, X); init(i<<1|1, m+1, r, X);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void propagate(int i, int l, int r){
        tree[i].mn += lazy[i], tree[i].mx += lazy[i];
        if (l!=r){
            lazy[i<<1] += lazy[i];
            lazy[i<<1|1] += lazy[i];
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    Node query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return O;
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
    }
    int lower_bound(int i, int l, int r, int h, Node prv){
        propagate(i, l, r);
        auto cur = tree[i] + prv;
        if (cur.mx - cur.mn<h) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int retr = lower_bound(i<<1|1, m+1, r, h, prv);
        if (retr!=-1) return retr;

        cur = tree[i<<1|1] + prv;
        return lower_bound(i<<1, l, m, h, cur);
    }
}tree;

void solve(int T){
    /*if (T==5){
        for (int i=0;i<=n;i++) printf(" %d", tree.query(1, 0, n, i, i).mx);
        printf("\n");
    }*/
    auto N = tree.query(1, 0, n, 0, n);

    int ans = -1;
    if (N.mx - N.mn < vmax){
        ///case 1
        auto E = tree.query(1, 0, n, n, n);
        if (vmax - (N.mx-E.mx) < v2) return;
        else if (vmax - (N.mx-E.mx) > v2){
            int delta = vmax - (N.mx-E.mx) - v2;
            int mx = vmax - delta;
            int o = mx - N.mx;

            if (o+N.mn<0 && E.mx-N.mn!=v2) return;
            ans = o;
        }
        else ans = vmax;
    }

    else{
        ///case 2
        int idx = tree.lower_bound(1, 0, n, vmax, Node(1e9, -1, -1e9, -1));
        N = tree.query(1, 0, n, idx, n);
        auto E = tree.query(1, 0, n, n, n);

        ans = vmax;
        if (N.imx==idx){
            ///case 2-1 (min)
            int val = E.mx - N.mn;
            if (val!=v2) return;
        }
        else{
            ///case 2-2 (max)
            int val = vmax - (N.mx - E.mx);
            if (val!=v2) return;
        }
    }

    if (T==INF) printf("infinity\n");
    else printf("%d %d\n", T, ans);
    exit(0);
}

int main(){
    scanf("%d %d %d", &n, &vmax, &v2);

    vector<pair<int, int>> V = {{INF, 0}};
    int prv = 0;
    for (int i=0;i<n;i++){
        char op;
        int cur;
        scanf(" %c %d", &op, &cur);
        a[i] = cur - prv;
        prv = cur;

        on[i] = 1;
        if (op=='+') p[i] = 1;
        if (i) V.emplace_back(a[i]-1, i);
    }
    --n;

    vector<int> X = {0};
    for (int i=1;i<=n;i++){
        X.push_back(X.back());
        if (p[i]) X.back()++;
        else X.back()--;
    }
    tree.init(1, 0, n, X);
    sort(V.begin(), V.end(), greater<pair<int, int>>());

    for (int i=0;i<(int)V.size();i++){
        if (i==0) {solve(INF); continue;}
        int r = i;
        for (;r<(int)V.size();r++){
            if (V[r].first!=V[i].first) break;
            if (p[V[r].second]) tree.update(1, 0, n, V[r].second, n, -1);
            else tree.update(1, 0, n, V[r].second, n, 1);
        }
        //printf("%d: %d %d\n", i, V[i].first, V[i].second);
        solve(V[i].first);
        i = r-1;
    }

    printf("0\n");
    return 0;
}

/*void _press(int &L, int &R, bool P){
    if (P){
        if (L>0) --L;
        if (R==0) {L = -1; return;}
        else if (R<vmax) --R;
    }
    else{
        if (R<vmax) ++R;
        if (L==vmax) {L = -1; return;}
        else if (L>0) ++L;
    }
}*/

Compilation message

mp3player.cpp: In function 'int main()':
mp3player.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |     scanf("%d %d %d", &n, &vmax, &v2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         scanf(" %c %d", &op, &cur);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2388 KB Output is correct
2 Correct 26 ms 2384 KB Output is correct
3 Correct 27 ms 2384 KB Output is correct
4 Correct 20 ms 2232 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2384 KB Output is correct
2 Correct 38 ms 2492 KB Output is correct
3 Correct 28 ms 2484 KB Output is correct
4 Correct 28 ms 2384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2616 KB Output is correct
2 Correct 10 ms 2604 KB Output is correct
3 Correct 40 ms 4100 KB Output is correct
4 Correct 26 ms 2524 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4468 KB Output is correct
2 Correct 52 ms 4484 KB Output is correct
3 Correct 46 ms 4360 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8872 KB Output is correct
2 Correct 90 ms 8616 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8880 KB Output is correct
2 Correct 86 ms 8612 KB Output is correct