제출 #47095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47095		SpaimaCarpatilor	Cultivation (JOI17_cultivation)	C++17	80 / 100	2057 ms	8184 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, sab;

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];
unsigned int relevantShifts[1209], relevantS1[609], relevantS2[609];
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 n = 0, m = 0, p = 0;
    for (int i=1; i<=nr; i++)
    {
        if (i > 1 && pos[i] - 1 <= updown)
            relevantS1[++n] = pos[i] - 1;
        if (pos[i] >= R && pos[i] - R <= updown)
            relevantS2[++m] = pos[i] - R;
    }
    merge (relevantS1 + 1, relevantS1 + n + 1, relevantS2 + 1, relevantS2 + m + 1, relevantShifts + 1);
    p = n + m, relevantShifts[++p] = updown;
    int j = 1, i = 1;
    for (int currPos = 1; currPos <= p; currPos ++)
    if (currPos == 1 || relevantShifts[currPos] != relevantShifts[currPos - 1])
    {
        unsigned int shift = relevantShifts[currPos];
        while (j <= nr && pos[j] <= R + shift)
            add (j), j++;
        while (pos[i + 1] - 1 < 1 + shift)
            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 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])
    {
        int val = x[i] - x[j];
        if (val < 0) val = -val;
        sab.insert (val - 1);
    }
for (auto a : sa)
    for (auto b : sb)
        sab.insert (a + b);
for (auto ab : sab)
{
    if (ans >= ab)
        solve (ab);
}
printf ("%d\n", ans);
return 0;
}

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

cultivation.cpp: In function 'void solve(int)':
cultivation.cpp:136:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (r < N && x[r + 1] <= t)
                         ~~~~~~~~~^~~~
cultivation.cpp:138:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (x[l] + updown < t && l <= N)
                ~~~~~~~~~~~~~~^~~
cultivation.cpp:149:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i > 1 && pos[i] - 1 <= updown)
                      ~~~~~~~~~~~^~~~~~~~~
cultivation.cpp:151:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pos[i] >= R && pos[i] - R <= updown)
             ~~~~~~~^~~~
cultivation.cpp:151:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pos[i] >= R && pos[i] - R <= updown)
                            ~~~~~~~~~~~^~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:217:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ans >= ab)
         ~~~~^~~~~
cultivation.cpp: In function 'void readAndSort()':
cultivation.cpp:174: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:175:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
cultivation.cpp:177: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