oj.uz

Submission #52786

# Submission time Handle Problem Language Result Execution time Memory
52786 2018-06-26T18:07:04 Z SpaimaCarpatilor Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1978 ms 113328 KB 
#include<bits/stdc++.h>

using namespace std;

int budget, N, M, K;

namespace solver0 {
    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);
    }

    void readAndSolve ()
    {
        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);
            v[x1].push_back ({{y1, y2}, +1});
            v[x2].push_back ({{y1, y2}, -1});
        }
        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 ++;
                if (x2 < N)
                    x2 ++, addLine (x2, +1);
                else
                    break;
            }
            addLine (x1, -1);
        }
        printf ("%d\n", L);
    }
};

namespace solverNon0 {
    const int maxX = 30000;
    int P, mi[4 * maxX + 100], lzy[4 * maxX + 100];
    vector < int > normX, normY;
    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 build (int nod, int st, int dr)
    {
        mi[nod] = lzy[nod] = 0;
        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);
        mi[nod] = min (mi[f1], mi[f2]);
    }

    void add (int L, int y1, int y2, int sg)
    {
        ///[y, y+L-1] intersects [y1, y2]
        ///y >= max (1, y1 - L + 1), y <= min (y2, M - L + 1)
        int l = max (1, y1 - L + 1), r = min (y2, M - L + 1);
        l = lower_bound (normY.begin (), normY.end (), l) - normY.begin () + 1;
        r = upper_bound (normY.begin (), normY.end (), r) - normY.begin ();
        if (l <= r)
            update (1, 1, P, l, r, sg);
    }

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

    bool ok (int L)
    {
        P = upper_bound (normY.begin (), normY.end (), M - L + 1) - normY.begin ();
        build (1, 1, P);
        int j = 0;
        for (int i=0; i + 1<normX.size (); i++)
        {
            addLine (L, normX[i], +1);
            int x2 = normX[i + 1] - 1;
            while (x2 - normX[j] + 1 > L)
                addLine (L, normX[j], -1), j ++;
            if (mi[1] <= budget && x2 >= L)
                return 1;
        }
        return 0;
    }

    void readAndSolve ()
    {
        scanf ("%d", &K);
        for (int i=1; i<=K; i++)
        {
            int x1, y1, x2, y2, c;
            scanf ("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
            normX.push_back (x1), normX.push_back (x2);
            normY.push_back (y2 + 1);
            v[x1].push_back ({{y1, y2}, +c});
            v[x2].push_back ({{y1, y2}, -c});
        }
        sort (normX.begin (), normX.end ());
        normX.erase (unique (normX.begin (), normX.end ()), normX.end ());
        normY.push_back (1), sort (normY.begin (), normY.end ());
        normY.erase (unique (normY.begin (), normY.end ()), normY.end ());
        normX.push_back (N + 1);
        int p = 1, u = min (N, M), mij, ras = 0;
        while (p <= u)
        {
            mij = (p + u) >> 1;
            if (ok (mij)) ras = mij, p = mij + 1;
            else u = mij - 1;
        }
        printf ("%d\n", ras);
    }
};

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

scanf ("%d %d", &N, &M);
scanf ("%d", &budget);
if (budget == 0)
{
    solver0::readAndSolve ();
    return 0;
}
solverNon0::readAndSolve ();
return 0;
}

Compilation message

pyramid_base.cpp: In function 'bool solverNon0::ok(int)':
pyramid_base.cpp:164:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i + 1<normX.size (); i++)
                       ~~~~~^~~~~~~~~~~~~~
pyramid_base.cpp: In function 'void solver0::readAndSolve()':
pyramid_base.cpp:78:25: 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:82:19: 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);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'void solverNon0::readAndSolve()':
pyramid_base.cpp:178:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &K);
         ~~~~~~^~~~~~~~~~
pyramid_base.cpp:182:19: 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);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:209: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:210:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &budget);
 ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 47664 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 48096 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 52632 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 85476 KB Output is correct
2 Correct 99 ms 86176 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 86176 KB Output is correct
2 Correct 94 ms 86176 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 86176 KB Output is correct
2 Correct 105 ms 86176 KB Output is correct
3 Correct 90 ms 86176 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 86176 KB Output is correct
2 Correct 387 ms 86176 KB Output is correct
3 Correct 311 ms 86176 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 86176 KB Output is correct
2 Correct 68 ms 86176 KB Output is correct
3 Correct 149 ms 86176 KB Output is correct
4 Correct 391 ms 86176 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 86176 KB Output is correct
2 Correct 774 ms 86176 KB Output is correct
3 Correct 198 ms 86176 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 86176 KB Output is correct
2 Correct 939 ms 86176 KB Output is correct
3 Correct 939 ms 86176 KB Output is correct
4 Correct 1004 ms 86176 KB Output is correct
5 Correct 961 ms 86176 KB Output is correct
6 Correct 189 ms 86176 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1050 ms 105816 KB Output is correct
2 Correct 387 ms 105816 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 109628 KB Output is correct
2 Correct 1409 ms 109628 KB Output is correct
3 Correct 644 ms 109628 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1386 ms 109628 KB Output is correct
2 Correct 1978 ms 113224 KB Output is correct
3 Correct 1854 ms 113328 KB Output is correct
4 Correct 1713 ms 113328 KB Output is correct
5 Correct 988 ms 113328 KB Output is correct