답안 #52768 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52768	2018-06-26T17:25:12 Z	SpaimaCarpatilor	Pyramid Base (IOI08_pyramid_base)	C++17	72 / 100	2169 ms	113100 KB

pyramid_base

#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 ++;
                //printf ("%d %d  %d\n", x1, x2, query ());
                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 (y1 + 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 ());
        P = normY.size (), 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:165: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:179:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &K);
         ~~~~~~^~~~~~~~~~
pyramid_base.cpp:183: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:210: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:211: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

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	47352 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	47364 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47548 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	43 ms	48356 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	52896 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	85536 KB	Output is correct
2	Correct	116 ms	86276 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	86276 KB	Output is correct
2	Correct	87 ms	86276 KB	Output is correct

Subtask #8
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	52 ms	86276 KB	Output is correct
2	Correct	115 ms	86276 KB	Output is correct
3	Correct	92 ms	86276 KB	Output is correct

Subtask #9
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	214 ms	86276 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	276 ms	86276 KB	Output is correct
2	Correct	74 ms	86276 KB	Output is correct
3	Incorrect	147 ms	86276 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #11
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	475 ms	86276 KB	Output is correct
2	Incorrect	792 ms	86276 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #12
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	387 ms	86276 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #13
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	922 ms	102556 KB	Output is correct
2	Correct	390 ms	102556 KB	Output is correct

Subtask #14
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1258 ms	106064 KB	Output is correct
2	Correct	1259 ms	108336 KB	Output is correct
3	Correct	634 ms	108336 KB	Output is correct

Subtask #15
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1541 ms	108336 KB	Output is correct
2	Correct	2005 ms	113076 KB	Output is correct
3	Correct	2169 ms	113100 KB	Output is correct
4	Correct	1830 ms	113100 KB	Output is correct
5	Correct	1056 ms	113100 KB	Output is correct