Submission #47030

#	Time	Username	Problem	Language	Result	Execution time	Memory
47030		SpaimaCarpatilor	Arranging Tickets (JOI17_arranging_tickets)	C++17	65 / 100	3169 ms	1760 KiB

arranging_tickets

#include<bits/stdc++.h>

using namespace std;

int N, M, b[3009], a[3009], l[3009], r[3009], c[3009], aib[3009];
vector < int > v[3009];

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

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

bool ok (int S)
{
    for (int cntFlipped = 0; cntFlipped <= M; cntFlipped ++)
    {
        for (int i=1; i<=N; i++)
        {
            int newA = a[i] + cntFlipped;
            if (newA < S) b[i] = 0;
            else b[i] = (newA + 1 - S) / 2;
        }
        for (int i=1; i<=N; i++)
            aib[i] = 0;
        bool ok = 1;
        int used = 0;
        priority_queue < int > PQ;
        for (int i=1; i<=N; i++)
        {
            for (auto r : v[i])
                PQ.push (r);
            int needed = max (0, b[i] - Q (N - i + 1));
            if (needed > PQ.size ())
            {
                ok = 0;
                break;
            }
            while (needed --)
            {
                int r = PQ.top ();
                PQ.pop (), used ++;
                U (N - r + 1, +1);
            }
        }
        if (ok == 1 && used <= cntFlipped)
            return 1;
    }
    return 0;
}

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

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

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
 ~~~~~~^~~~~~~~~~~~~~~~~
arranging_tickets.cpp:71:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &l[i], &r[i], &c[i]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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