Submission #1263646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263646		miniob	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	2 ms	4928 KiB

arranging_tickets

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

vector<pair<pair<long long, long long>, long long>> wyma;
long long roz[200007];
long long ile[200007];
long long sumakon[200007];
long long maxseg = -1, gdziemax, n, m;
vector<pair<long long, long long>> przechodzace[200007];
long long cof[200007];

bool spr(long long sr, long long ilezw)
{
    priority_queue<pair<long long, long long>> pq;
    long long suma = 0;
    for(long long i = 0; i < n + 3; i++)
    {
        sumakon[i] = 0;
    }
    long long cur = 0;
    long long usunl = 0;
    for(long long i = 1; i <= gdziemax; i++)
    {
        for(auto x : przechodzace[i])
        {
            pq.push(x);
            cur += x.second;
            suma += x.second;
            sumakon[x.first] += x.second; 
        }
        while(cur > sr)
        {
            auto x = pq.top();
            pq.pop();
            long long minn = min(cur - sr, x.second);
            x.second -= minn;
            cur -= minn;
            usunl += minn;
            if(x.second > 0)
            {
                pq.push(x);
            }
        }
    }
    while(!pq.empty())
    {
        pq.pop();
    }
    cur = 0;
    long long usup = 0;
    for(long long j = gdziemax; j <= n - 1; j++)
    {
        if(sumakon[j] > 0)
        {
            long long remain = sumakon[j];
            while(remain > 0)
            {
                pq.push({j, remain});
                cur += remain;
                remain = 0;
            }
        }
        while(cur > sr)
        {
            auto x = pq.top();
            pq.pop();
            long long minn = min(cur - sr, x.second);
            x.second -= minn;
            cur -= minn;
            usup += minn;
            if(x.second > 0)
            {
                pq.push({x.first, x.second});
            }
        }
    }
    if(usunl + usup <= suma)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{
    cin >> n >> m;
    for(long long i = 0; i < m; i++)
    {
        long long a, b, c;
        cin >> a >> b >> c;
        if(a > b)
        {
            swap(a, b);
        }
        wyma.push_back({{a, b - 1}, c});
        roz[a] += c;
        roz[b] -= c;
    }
    for(long long i = 1; i <= n; i++)
    {
        ile[i] = ile[i - 1] + roz[i];
        if(maxseg < ile[i])
        {
            maxseg = ile[i]; 
            gdziemax = i;
        }
    }
    for(auto x : wyma)
    {
        if(x.first.first <= gdziemax && gdziemax <= x.first.second)
        {
            przechodzace[x.first.first].push_back({x.first.second, x.second});
        }
    }
    long long l = 0, r = maxseg;
    while(l < r)
    {
        long long sr = (l + r) / 2;
        if(spr(sr, maxseg - sr) || spr(sr, maxseg - sr + 1))
        {
            r = sr;
        }
        else
        {
            l = sr + 1;
        }
    }
    cout << l << endl;
    return 0;
}

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