Submission #52762

#	Time	Username	Problem	Language	Result	Execution time	Memory
52762		SpaimaCarpatilor	Pyramid Base (IOI08_pyramid_base)	C++17	65 / 100	2359 ms	138552 KiB

pyramid_base

#include<bits/stdc++.h>

using namespace std;

int budget, N, M, K;
const int maxX = 1000000;

int mi[4 * maxX + 100], b[4 * maxX + 100], l[4 * maxX + 100], r[4 * maxX + 100], lzy[4 * maxX + 100];
void split (int &nod, int &f1, int &f2)
{
    if (lzy[nod] == 0) return ;
    lzy[f1] += lzy[nod], mi[f1] += lzy[nod];
    lzy[f2] += lzy[nod], mi[f2] += lzy[nod];
    lzy[nod] = 0;
}

void refresh (int &nod, int &f1, int &f2, int &mij, int &st, int &dr)
{
    if (mi[f1] == mi[f2])
        b[nod] = max ({b[f1], b[f2], r[f1] + l[f2]}),
        l[nod] = (l[f1] == mij - st + 1 ? l[f1] + l[f2] : l[f1]),
        r[nod] = (r[f2] == dr - mij ? r[f2] + r[f1] : r[f2]);
    else
    if (mi[f1] < mi[f2])
        b[nod] = b[f1],
        l[nod] = l[f1], r[nod] = 0;
    else
        b[nod] = b[f2],
        r[nod] = r[f2], l[nod] = 0;
}

void build (int nod, int st, int dr)
{
    mi[nod] = 0, l[nod] = r[nod] = b[nod] = dr - st + 1;
    if (st == dr) return ;
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    build (f1, st, mij);
    build (f2, mij + 1, dr);
}

void update (int nod, int st, int dr, int x, int y, int xtra)
{
    if (x <= st && dr <= y)
    {
        mi[nod] += xtra, lzy[nod] += xtra;
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    split (nod, f1, f2);
    if (x <= mij) update (f1, st, mij, x, y, xtra);
    if (mij < y) update (f2, mij + 1, dr, x, y, xtra);
    refresh (nod, f1, f2, mij, st, dr);
}

int query ()
{
    if (mi[1] != 0) return 0;
    return b[1];
}

void add (int y1, int y2, int sg)
{
    //printf ("[%d %d] %d\n", y1, y2, sg);
    update (1, 1, M, y1, y2, sg);
}

vector < pair < pair < int, int >, int > > v[maxX + 100];
void addLine (int line, int sg)
{
    for (auto it : v[line])
        if (sg * it.second > 0)
            add (it.first.first, it.first.second, it.second);
}

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

scanf ("%d %d", &N, &M);
scanf ("%d", &budget);
scanf ("%d", &K), build (1, 1, M);
for (int i=1; i<=K; i++)
{
    int x1, y1, x2, y2, c;
    scanf ("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
    if (budget == 0) c = (c > 0);
    v[x1].push_back ({{y1, y2}, +c});
    v[x2].push_back ({{y1, y2}, -c});
}
int L = 0, x2 = 0;
for (int x1=1; x1<=N - L; x1++)
{
    while (x2 < x1 + L)
        x2 ++, addLine (x2, +1);
    while (query () > L)
    {
        L ++;
        //printf ("%d %d  %d\n", x1, x2, query ());
        if (x2 < N)
            x2 ++, addLine (x2, +1);
        else
            break;
    }
    addLine (x1, -1);
}
printf ("%d\n", L);
return 0;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
 ~~~~~~^~~~~~~~~~~~~~~~~
pyramid_base.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &budget);
 ~~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &K), build (1, 1, M);
 ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
pyramid_base.cpp:86:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10