oj.uz

Submission #981541

# Submission time Handle Problem Language Result Execution time Memory
981541 2024-05-13T10:14:16 Z Double_Slash MP3 Player (CEOI10_mp3player) C++17
70 / 100
 234 ms 18640 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 val.a.s;
            if (val.b.rmx > mx - v2) return val.a.s;
            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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1112 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 9 ms 1124 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4436 KB Output is correct
2 Correct 68 ms 5156 KB Output is correct
3 Correct 64 ms 4956 KB Output is correct
4 Correct 58 ms 4700 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4696 KB Output is correct
2 Correct 63 ms 6016 KB Output is correct
3 Correct 63 ms 5800 KB Output is correct
4 Correct 74 ms 5212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5708 KB Output is correct
2 Correct 83 ms 5700 KB Output is correct
3 Correct 94 ms 7768 KB Output is correct
4 Correct 86 ms 6340 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8128 KB Output is correct
2 Correct 147 ms 10128 KB Output is correct
3 Correct 131 ms 9308 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 13396 KB Output is correct
2 Correct 216 ms 18636 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 15440 KB Output is correct
2 Correct 234 ms 18640 KB Output is correct