oj.uz

Submission #981190

# Submission time Handle Problem Language Result Execution time Memory
981190 2024-05-13T01:54:00 Z Double_Slash MP3 Player (CEOI10_mp3player) C++17
30 / 100
 220 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 -1;
            if (val.b.rmx > mx - v2) return -1;
            return val.a.s;
        }
        if (val.a.mmx >= mx) {
            val = st.query(val.a.mmxi + 1, n);
            return mx + val.a.s == v2 ? mx + val.a.s : -1;
        } else {
            val = st.query(val.b.mmxi + 1, n);
            return val.a.s == v2 ? val.a.s : -1;
        }
    };
    pint ans;
    for (auto [t, v]: events) {
        if (~calc()) {
            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()) cout << "infinity\n";
    else cout << ans.first << " " << ans.second << endl;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 868 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Incorrect 9 ms 1132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1116 KB Output is correct
2 Correct 9 ms 1116 KB Output is correct
3 Correct 13 ms 1116 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4188 KB Output is correct
2 Incorrect 66 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4700 KB Output is correct
2 Incorrect 63 ms 5724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 5696 KB Output is correct
2 Correct 71 ms 5724 KB Output is correct
3 Incorrect 130 ms 7980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 8264 KB Output is correct
2 Incorrect 149 ms 10068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 13404 KB Output is correct
2 Correct 217 ms 18640 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 15576 KB Output is correct
2 Correct 220 ms 18640 KB Output is correct