oj.uz

Submission #440845

# Submission time Handle Problem Language Result Execution time Memory
440845 2021-07-03T11:20:05 Z prvocislo MP3 Player (CEOI10_mp3player) C++17
100 / 100
 104 ms 7884 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5452 KB Output is correct
2 Correct 6 ms 5452 KB Output is correct
3 Correct 8 ms 5464 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5452 KB Output is correct
2 Correct 5 ms 5452 KB Output is correct
3 Correct 5 ms 5452 KB Output is correct
4 Correct 5 ms 5456 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5512 KB Output is correct
2 Correct 7 ms 5452 KB Output is correct
3 Correct 7 ms 5464 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5828 KB Output is correct
2 Correct 19 ms 5948 KB Output is correct
3 Correct 20 ms 5928 KB Output is correct
4 Correct 16 ms 5836 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6044 KB Output is correct
2 Correct 22 ms 6044 KB Output is correct
3 Correct 21 ms 5968 KB Output is correct
4 Correct 17 ms 5964 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6092 KB Output is correct
2 Correct 32 ms 6048 KB Output is correct
3 Correct 29 ms 6192 KB Output is correct
4 Correct 19 ms 6072 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6524 KB Output is correct
2 Correct 37 ms 6524 KB Output is correct
3 Correct 28 ms 6416 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 7768 KB Output is correct
2 Correct 64 ms 7884 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7788 KB Output is correct
2 Correct 65 ms 7768 KB Output is correct