oj.uz

Submission #981561

# Submission time Handle Problem Language Result Execution time Memory
981561 2024-05-13T10:36:09 Z Double_Slash MP3 Player (CEOI10_mp3player) C++17
100 / 100
 227 ms 17360 KB 
#include <bits/stdc++.h>
#define debug(x) [&] () { auto _x = x; cerr << __LINE__ << ": " << #x << " = " << _x << endl; }()

using namespace std;
typedef long long ll;
typedef pair<int, int> pint;
#define all(x) x.begin(), x.end()

const int INF = 1e6;

struct MaxSum {
    int lmx, lmxi, mmx, mmxi, rmx, s;

    MaxSum() {}

    MaxSum(int i, int x) : lmx(x), lmxi(i), mmx(x), mmxi(i), rmx(x), s(x) {}

    MaxSum operator+(const MaxSum &o) {
        MaxSum ret;
        ret.s = s + o.s;
        tie(ret.lmx, ret.lmxi) = max({pint{lmx, lmxi}, pint{s + o.lmx, o.lmxi}});
        ret.rmx = max(o.rmx, rmx + o.s);
        tie(ret.mmx, ret.mmxi) = max({
            pint{mmx, mmxi},
            pint{o.mmx, o.mmxi},
            pint{rmx + o.lmx, o.lmxi}
        });
        return ret;
    }
};

struct Val {
    MaxSum a, b;

    Val() {}

    Val(int i, int x) : a(i, x), b(i, -x) {}

    Val operator+(const Val &o) {
        Val ret;
        ret.a = a + o.a, ret.b = b + o.b;
        return ret;
    }
};

struct St {
    int n;
    vector<Val> st;

    St(int n) : n(n), st(n << 1) {
        for (int i = 0; i < n; ++i) st[i + n] = Val(i, 0);
        for (int i = n; --i;) st[i] = st[i << 1] + st[i << 1 | 1];
    }

    Val query(int l, int r) {
        Val lagg{0, 0}, ragg{n, 0};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lagg = lagg + st[l++];
            if (r & 1) ragg = st[--r] + ragg;
        }
        return lagg + ragg;
    }

    void update(int i, const Val &v) {
        for (st[i += n] = v; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
    }
};

int n, mx, v2;

int main() {
    cin >> n >> mx >> v2;
    map<int, vector<pint>> events;
    for (int last, i = 0; i < n; ++i) {
        char c;
        int t;
        cin >> c >> t;
        if (i) events[t - last].emplace_back(i, c == '+' ? 1 : -1);
        last = t;
    }
    St st(n);
    auto calc = [&] () {
        int l = n;
        for (int j = 18; ~--j;) {
            if (l - (1 << j) >= 0) {
                auto val = st.query(l - (1 << j), n);
                if (max(val.a.mmx, val.b.mmx) < mx) l -= 1 << j;
            }
        }
        auto val = st.query(max(0, l - 1), n);
        if (l == 0) {
            if (val.a.rmx > v2) return -1;
            if (val.b.rmx > mx - v2) return -1;
            return v2;
        }
        if (val.a.mmx >= mx) {
            val = st.query(val.a.mmxi + 1, n);
            return mx + val.a.s;
        } else {
            val = st.query(val.b.mmxi + 1, n);
            return val.a.s;
        }
    };
    pint ans;
    for (auto [t, v]: events) {
        if (calc() == v2) {
            ans.first = t - 1;
            st.update(0, {0, INF});
            if (calc() == v2) ans.second = mx;
            else ans.second = v2 - st.query(1, n).a.s;
            st.update(0, {0, 0});
        }
        for (auto [i, x]: v) {
            st.update(i, {i, x});
        }
    }
    if (calc() == v2) cout << "infinity\n";
    else cout << ans.first << " " << ans.second << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 856 KB Output is correct
2 Correct 2 ms 812 KB Output is correct
3 Correct 7 ms 896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 4 ms 760 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 856 KB Output is correct
2 Correct 9 ms 1112 KB Output is correct
3 Correct 9 ms 1116 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3928 KB Output is correct
2 Correct 65 ms 4952 KB Output is correct
3 Correct 73 ms 4896 KB Output is correct
4 Correct 58 ms 4696 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4440 KB Output is correct
2 Correct 62 ms 5512 KB Output is correct
3 Correct 62 ms 5504 KB Output is correct
4 Correct 73 ms 4952 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5212 KB Output is correct
2 Correct 66 ms 5464 KB Output is correct
3 Correct 91 ms 7516 KB Output is correct
4 Correct 89 ms 5916 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 7828 KB Output is correct
2 Correct 151 ms 9576 KB Output is correct
3 Correct 125 ms 8792 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 12092 KB Output is correct
2 Correct 216 ms 17360 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 14364 KB Output is correct
2 Correct 215 ms 17360 KB Output is correct