Submission #440845

#	Time	Username	Problem	Language	Result	Execution time	Memory
440845		prvocislo	MP3 Player (CEOI10_mp3player)	C++17	100 / 100	104 ms	7884 KiB

mp3player

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1 << 17, inf = 2e9 + 5;
int n, vmax, v2;
struct node
{ 
    int mi, ma, d; // hranice kde je funkcia f konstantna, d = f(mi) - mi
    node():mi(0), ma(vmax), d(0) {}
    node(int s):mi(max(0, -s)), ma(min(vmax, vmax-s)), d(s) {}
    node(int MI, int MA, int D):mi(MI), ma(MA), d(D) {}
} st[maxn*2];
node merge(const node &l, const node &r)
{
    if (l.mi + l.d >= r.ma) return node(vmax, vmax, r.ma + r.d - vmax);
    if (l.ma + l.d <= r.mi) return node(vmax, vmax, r.mi + r.d - vmax);
    return node(max(l.mi, r.mi-l.d), min(l.ma, r.ma-l.d), l.d+r.d);
}
int l[maxn*2], r[maxn*2], t[maxn], ord[maxn], s[maxn];
void update(int x, int s, int vr = 0)
{
    if (x < l[vr] || r[vr] < x) return;
    if (l[vr] == r[vr]) 
    {
        st[vr] = node(s);
        return;
    }
    update(x, s, vr*2+1), update(x, s, vr*2+2);
    st[vr] = merge(st[vr*2+1], st[vr*2+2]);
}
bool cmp(int i, int j) 
{
    return t[i] < t[j];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = maxn - 1; i < maxn * 2; i++) l[i] = r[i] = i - (maxn - 1);
    for (int i = maxn - 2; i >= 0; i--) l[i] = l[i*2+1], r[i] = r[i*2+2], st[i] = node();
    cin >> n >> vmax >> v2;
    for (int i = 0; i < maxn * 2; i++) st[i] = node();
    for (int i = 0; i < n; i++)
    {
        char c; cin >> c >> t[i];
        s[i] = (c == '+' ? 1 : -1);
        ord[i] = i;
    }
    for (int i = n - 1; i > 0; i--) t[i] -= t[i-1];
    t[0] = inf + 1;
    sort(ord, ord + n, cmp);
    int tans = t[ord[0]] - 1, vans = v2;
    for (int i = 0; i < n - 1; i++)
    {
        update(ord[i], s[ord[i]]);
        if (t[ord[i]] < t[ord[i + 1]])
        {
            if (st[0].ma + st[0].d == v2) 
                tans = t[ord[i + 1]] - 1, vans = vmax;
            else if (st[0].mi + st[0].d < v2 && v2 < st[0].ma + st[0].d) 
                tans = t[ord[i + 1]] - 1, vans = v2 - st[0].d;
            else if (st[0].mi + st[0].d == v2)
                tans = t[ord[i + 1]] - 1, vans = st[0].mi;
        }
    }
    if (tans == inf) cout << "infinity\n";
    else cout << tans << " " << vans << "\n";
    return 0;
}

• 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