oj.uz

Submission #486397

# Submission time Handle Problem Language Result Execution time Memory
486397 2021-11-11T14:54:55 Z Rainbowbunny MP3 Player (CEOI10_mp3player) C++17
100 / 100
 70 ms 9144 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

int n, vmax, v2;
int c[MAXN];
char a[MAXN];
vector <pair <int, int> > V;

struct Node
{
    int l, r, l1, r1;
    Node() {}
} IT[4 * MAXN];

void Debug(Node A)
{
    cout << "{" << A.l << ' ' << A.r << ' ' << A.l1 << ' ' << A.r1 << "}\n";
}

int eval(int pos, Node &F)
{
    if(pos <= F.l)
    {
        return F.l1;
    }
    if(pos >= F.r)
    {
        return F.r1;
    }
    return F.l1 + (pos - F.l);
}

Node Merge(Node A, Node B)
{
    Node C;
    C.l = A.l + max(B.l - A.l1, 0);
    C.r = A.r + min(B.r - A.r1, 0);
    C.l1 = eval(eval(C.l, A), B);
    C.r1 = eval(eval(C.r, A), B);
    if(C.l >= C.r)
    {
        C.l = vmax;
        C.r = 0;
        assert(C.l1 == C.r1);
    }
    // Debug(A);
    // Debug(B);
    // Debug(C);
    return C;
}

void Update(int node, int l, int r, int id, int v)
{
    if(l > id or r < id)
    {
        return;
    }
    if(l == r)
    {
        if(v == 1)
        {
            IT[node].l = 0;
            IT[node].r = vmax - 1;
            IT[node].l1 = 1;
            IT[node].r1 = vmax;
        }
        else
        {
            IT[node].l = 1;
            IT[node].r = vmax;
            IT[node].l1 = 0;
            IT[node].r1 = vmax - 1;
        }
        return;
    }
    int mid = (l + r) >> 1;
    Update(node << 1, l, mid, id, v);
    Update(node << 1 | 1, mid + 1, r, id, v);
    IT[node] = Merge(IT[node << 1], IT[node << 1 | 1]);
}

int ansT, ansV;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> vmax >> v2;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i] >> c[i];
        if(i)
        {
            V.emplace_back(c[i] - c[i - 1], i);
        }
    }
    sort(V.begin(), V.end());
    for(int i = 1; i < 4 * MAXN; i++)
    {
        IT[i].l = 0;
        IT[i].r = vmax;
        IT[i].l1 = 0;
        IT[i].r1 = vmax;
    }
    int pt = 0;
    ansT = V[0].first - 1;
    ansV = v2;
    while(pt + 1 < n)
    {
        int cur = pt;
        while(cur + 1 < n and V[cur].first == V[pt].first)
        {
            int id = V[cur].second;
            if(a[id] == '+')
            {
                Update(1, 1, n, id, 1);
            }
            else
            {
                Update(1, 1, n, id, -1);
            }
            
            cur++;
        }
        if(IT[1].l1 <= v2 and v2 <= IT[1].r1)
        {
            if(cur + 1 == n)
            {
                cout << "infinity\n";
                return 0;
            }
            ansT = V[cur].first - 1;
            if(v2 == IT[1].r1)
            {
                ansV = vmax;
            }
            else
            {
                ansV = v2 - IT[1].l1 + IT[1].l;
            }
        }
        pt = cur;
    }
    // cout << IT[1].l1 << ' ' << IT[1].r1 << '\n';
    
    cout << ansT << ' ' << ansV << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6604 KB Output is correct
2 Correct 5 ms 6604 KB Output is correct
3 Correct 4 ms 6616 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6568 KB Output is correct
2 Correct 5 ms 6532 KB Output is correct
3 Correct 4 ms 6552 KB Output is correct
4 Correct 5 ms 6604 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6604 KB Output is correct
2 Correct 6 ms 6680 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6900 KB Output is correct
2 Correct 14 ms 7248 KB Output is correct
3 Correct 17 ms 7248 KB Output is correct
4 Correct 16 ms 7120 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6936 KB Output is correct
2 Correct 15 ms 7248 KB Output is correct
3 Correct 18 ms 7256 KB Output is correct
4 Correct 15 ms 7192 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6996 KB Output is correct
2 Correct 19 ms 7032 KB Output is correct
3 Correct 19 ms 7116 KB Output is correct
4 Correct 15 ms 6992 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7260 KB Output is correct
2 Correct 24 ms 7764 KB Output is correct
3 Correct 26 ms 7636 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7872 KB Output is correct
2 Correct 58 ms 9144 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7892 KB Output is correct
2 Correct 44 ms 9112 KB Output is correct