Submission #90354

#	Time	Username	Problem	Language	Result	Execution time	Memory
90354		Alexa2001	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	6 ms	4988 KiB

arranging_tickets

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

priority_queue<int> heap;
int start[Nmax], finish[Nmax], add[Nmax], dp[Nmax];
vector<int> v[Nmax];
int n, m, i;

bool check(int L)
{
    int i, need = 0, nr;

    while(heap.size()) heap.pop();

    for(i=1; i<=n; ++i) finish[i] = 0;

    for(i=1; i<=n; ++i)
    {
        start[i] = v[i].size(); add[i] = 0;
        for(auto it : v[i]) finish[it] ++;
    }

    dp[0] = L;
    for(i=1; i<n; ++i)
    {
        for(auto it : v[i]) heap.push(it);

        dp[i] = dp[i-1] + start[i] - finish[i] + add[i];

        while(dp[i] > L && need <= L)
        {
            assert(heap.size());

            dp[i] -= 2;
            nr = heap.top();
            heap.pop();
            add[nr] += 2;
            ++need;
        }

        if(need > L) return 0;
    }

    return (need <= L);
}

int main()
{
  //  freopen("input", "r", stdin);

    cin >> n >> m;

    int i, x, y, C;
    for(i=1; i<=m; ++i)
    {
        cin >> x >> y >> C;
        if(x > y) swap(x, y);
        v[x].push_back(y);
    }

    for(i=1; i<=n; ++i) sort(v[i].begin(), v[i].end());

    int st = 0, dr = m, mid;

    while(st <= dr)
    {
        mid = (st+dr) / 2;
        if(check(mid)) dr = mid-1;
            else st = mid+1;
    }

    cout << st << '\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15