제출 #47096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47096		SpaimaCarpatilor	Cultivation (JOI17_cultivation)	C++17	80 / 100	2076 ms	2428 KiB

cultivation

#include<bits/stdc++.h>

using namespace std;

int N, R, C, x[309], y[309], precalc[309][309][3];
const int INF = 1e9 + 100;
unsigned int ans = UINT_MAX;
set < int > sa, sb;

namespace ds {
    multiset < int > xs, dx;

    void init ()
    {
        xs.clear (), dx.clear ();
    }

    void delDif (int x)
    {
        dx.erase (dx.find (x));
    }

    void add (int x)
    {
        if (xs.find (x) != xs.end ()) xs.insert (x);
        else
        {
            xs.insert (x);
            auto it1 = xs.lower_bound (x), it2 = xs.upper_bound (x);
            if (it1 != xs.begin () && it2 != xs.end ())
                it1 --,
                delDif ((*it2) - (*it1)),
                it1 ++;
            if (it1 != xs.begin ())
                it1 --,
                dx.insert (x - (*it1));
            if (it2 != xs.end ())
                dx.insert ((*it2) - x);
        }
    }

    void del (int x)
    {
        if (xs.count (x) >= 2) xs.erase (xs.find (x));
        else
        {
            auto it1 = xs.lower_bound (x), it2 = xs.upper_bound (x);
            if (it1 != xs.begin () && it2 != xs.end ())
                it1 --,
                dx.insert ((*it2) - (*it1)),
                it1 ++;
            if (it1 != xs.begin ())
                it1 --,
                delDif (x - (*it1));
            if (it2 != xs.end ())
                delDif ((*it2) - x);
            xs.erase (x);
        }
    }

    int maxDif ()
    {
        if (dx.empty ()) return 0;
        return *(dx.rbegin ());
    }

    int getA ()
    {
        if (xs.empty ()) return INF;
        return (*xs.begin ()) - 1;
    }

    int getB ()
    {
        if (xs.empty ()) return INF;
        return C - (*xs.rbegin ());
    }

    void store (int &a, int &b, int &df)
    {
        a = getA ();
        b = getB ();
        df = maxDif () - 1;
    }
};

unsigned int pos[1209];
int nr, stat[1209][3];
int dq[3][1209], fst[3], lst[3];

void clearDeque ()
{
    for (int i=0; i<3; i++)
        fst[i] = 1, lst[i] = 0;
}

void add (int pos)
{
    for (int i=0; i<3; i++)
    {
        while (fst[i] <= lst[i] && stat[dq[i][lst[i]]][i] <= stat[pos][i])
            lst[i] --;
        dq[i][++lst[i]] = pos;
    }
}

void del (int pos)
{
    for (int i=0; i<3; i++)
        while (fst[i] <= lst[i] && dq[i][fst[i]] <= pos)
            fst[i] ++;
}

int getSum ()
{
    if (fst[0] > lst[0]) return 2 * INF;
    int minA = stat[dq[0][fst[0]]][0], minB = stat[dq[1][fst[1]]][1], minAB = stat[dq[2][fst[2]]][2];
    return max (minA + minB, minAB);
}

unsigned int relevantXs[609], relevantX1[309], relevantX2[309];
void solve (int updown)
{
    ds::init ();
    clearDeque ();
    for (int i=1; i<=N; i++)
        relevantX2[i] = x[i] + updown + 1;
    merge (relevantX1 + 1, relevantX1 + N + 1, relevantX2 + 1, relevantX2 + N + 1, relevantXs + 1);

    nr = 1, pos[1] = 0, stat[1][0] = INF, stat[1][1] = INF, stat[1][2] = -1;
    int l = 1, r = 0;
    for (int currPos = 1; currPos <= 2 * N; currPos ++)
    {
        unsigned int t = relevantXs[currPos];
        while (r < N && x[r + 1] <= t)
            r ++;
        while (x[l] + updown < t && l <= N)
            l ++;
        nr ++, pos[nr] = t;
        stat[nr][0] = precalc[l][r][0];
        stat[nr][1] = precalc[l][r][1];
        stat[nr][2] = precalc[l][r][2];
    }
    pos[nr + 1] = UINT_MAX;
    int i = 1;
    for (int j=1; j<=nr && pos[j] <= updown + R; j++)
    {
        unsigned int rightEnd = min ((unsigned int) updown + R, pos[j + 1] - 1);
        add (j);
        if (rightEnd >= R)
        {
            while (pos[i + 1] - 1 < rightEnd - R + 1)
                del (i), i ++;
            unsigned int curr = updown + getSum ();
            if (curr < ans)
                ans = curr;
        }
    }
}

void readAndSort ()
{
    pair < int, int > point[309];
    scanf ("%d %d\n", &R, &C);
    scanf ("%d", &N);
    for (int i=1; i<=N; i++)
        scanf ("%d %d", &point[i].first, &point[i].second);
    sort (point + 1, point + N + 1);
    for (int i=1; i<=N; i++)
        x[i] = point[i].first, y[i] = point[i].second;
}

void doPrecalc ()
{
    for (int i=1; i<=N + 1; i++)
    {
        ds::init ();
        ds::store (precalc[i][i - 1][0], precalc[i][i - 1][1], precalc[i][i - 1][2]);
        for (int j=i; j<=N; j++)
            ds::add (y[j]),
            ds::store (precalc[i][j][0], precalc[i][j][1], precalc[i][j][2]);
    }
}

int cntsab, sab[309 * 309 * 3 / 2];
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

readAndSort ();
doPrecalc ();
for (int i=1; i<=N; i++)
    sa.insert (x[i] - 1), sb.insert (R - x[i]), relevantX1[i] = x[i];
for (int i=1; i<=N; i++)
    for (int j=i + 1; j<=N; j++)
        if (x[i] != x[j])
            sab[++cntsab] = x[j] - x[i] - 1;
int minVal = 0;
for (int i=1; i<N; i++)
    if (x[i + 1] - x[i] - 1 > minVal)
        minVal = x[i + 1] - x[i] - 1;
for (auto a : sa)
    for (auto b : sb)
        sab[++cntsab] = a + b;
sort (sab + 1, sab + cntsab + 1);
for (int i=1; i<=cntsab; i++)
    if ((i == 1 || sab[i] != sab[i - 1]) && ans > sab[i] && sab[i] >= minVal)
        solve (sab[i]);
printf ("%d\n", ans);
return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cultivation.cpp: In function 'void solve(int)':
cultivation.cpp:135:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (r < N && x[r + 1] <= t)
                         ~~~~~~~~~^~~~
cultivation.cpp:137:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (x[l] + updown < t && l <= N)
                ~~~~~~~~~~~~~~^~~
cultivation.cpp:146:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=1; j<=nr && pos[j] <= updown + R; j++)
                            ~~~~~~~^~~~~~~~~~~~~
cultivation.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (rightEnd >= R)
             ~~~~~~~~~^~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:208:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ((i == 1 || sab[i] != sab[i - 1]) && ans > sab[i] && sab[i] >= minVal)
                                             ~~~~^~~~~~~~
cultivation.cpp: In function 'void readAndSort()':
cultivation.cpp:164:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d\n", &R, &C);
     ~~~~~~^~~~~~~~~~~~~~~~~~~
cultivation.cpp:165:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
cultivation.cpp:167:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &point[i].first, &point[i].second);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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