Submission #486397

#	Time	Username	Problem	Language	Result	Execution time	Memory
486397		Rainbowbunny	MP3 Player (CEOI10_mp3player)	C++17	100 / 100	70 ms	9144 KiB

mp3player

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