Submission #981561

#	Time	Username	Problem	Language	Result	Execution time	Memory
981561		Double_Slash	MP3 Player (CEOI10_mp3player)	C++17	100 / 100	227 ms	17360 KiB

mp3player

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