Submission #47036

#	Time	Username	Problem	Language	Result	Execution time	Memory
47036		SpaimaCarpatilor	Arranging Tickets (JOI17_arranging_tickets)	C++17	100 / 100	3770 ms	30680 KiB

arranging_tickets

#include<bits/stdc++.h>

using namespace std;

long long maxA, N, M, l[100009], r[100009], c[100009];
long long sumC, b[200009], a[200009], aib[200009];
vector < pair < long long, long long > > v[200009];

void U (long long pos, long long val)
{
    while (pos <= N)
        aib[pos] += val,
        pos += pos - (pos & (pos - 1));
}

long long Q (long long pos)
{
    long long sum = 0;
    while (pos)
        sum += aib[pos],
        pos &= pos - 1;
    return sum;
}

bool getVerdict (long long S, long long cntFlipped)
{
    if (cntFlipped > sumC) return 0;
    for (long long i=1; i<=N; i++)
    {
        long long newA = a[i] + cntFlipped;
        if (newA < S) b[i] = 0;
        else b[i] = (newA + 1 - S) / 2;
    }
    for (long long i=1; i<=N; i++)
        aib[i] = 0;
    long long used = 0;
    priority_queue < pair < long long, long long > > PQ;
    for (long long i=1; i<=N; i++)
    {
        for (auto r : v[i])
            PQ.push (r);
        long long needed = max (0LL, b[i] - Q (N - i + 1));
        while (!PQ.empty ())
        {
            auto curr = PQ.top ();
            PQ.pop ();
            long long f = min (needed, (long long) curr.second);
            used += f, needed -= f;
            U (N - curr.first + 1, +f);
            if (f != curr.second)
                PQ.push ({curr.first, curr.second - f});
            if (needed == 0)
                break;
        }
        if (needed > 0) return 0;
    }
    return (used <= cntFlipped);
}

bool ok (long long S)
{
    if (S >= maxA) return 1;
    if (getVerdict (S, maxA - S)) return 1;
    if (getVerdict (S, maxA - S + 1)) return 1;
    return 0;
}

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

scanf ("%lld %lld", &N, &M);
///N links: 1-2, 2-3, .., N-1
for (long long i=1; i<=M; i++)
{
    scanf ("%lld %lld %lld", &l[i], &r[i], &c[i]), sumC += c[i];
    if (l[i] > r[i]) swap (l[i], r[i]);
    a[l[i]] += c[i], a[r[i]] -= c[i];
    v[l[i]].push_back ({r[i] - 1, c[i]});
}
long long p = 1, u = 0, mij, ras;
for (long long i=1; i<=N; i++)
    a[i] += a[i - 1], u = max (u, a[i]);
maxA = u;
while (p <= u)
{
    mij = (p + u) >> 1;
    if (ok (mij)) ras = mij, u = mij - 1;
    else p = mij + 1;
}
printf ("%lld\n", ras);
return 0;
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%lld %lld", &N, &M);
 ~~~~~~^~~~~~~~~~~~~~~~~~~~~
arranging_tickets.cpp:77:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%lld %lld %lld", &l[i], &r[i], &c[i]), sumC += c[i];
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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