Submission #47072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
47072	2018-04-27T09:05:29 Z	SpaimaCarpatilor	Cultivation (JOI17_cultivation)	C++17	Compilation error	0 ms	0 KB

cultivation

#include<bits/stdc++.h>

using namespace std;

int N, R, C, x[309], y[309];
const int INF = 1e9 + 100;
long long ans = 1LL << 60;
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 ());
    }
}

long long pos[1209];
int nr, data[1209][3];
vector < pair < long long, int > > events;
deque < int > dq[3];

void clearDeque ()
{
    for (int i=0; i<3; i++)
        while (!dq[i].empty ())
            dq[i].pop_back ();
}

void add (int pos)
{
    for (int i=0; i<3; i++)
    {
        while (!dq[i].empty () && data[dq[i].back ()][i] <= data[pos][i])
            dq[i].pop_back ();
        dq[i].push_back (pos);
    }
}

void del (int pos)
{
    for (int i=0; i<3; i++)
        while (!dq[i].empty () && dq[i].front () <= pos)
            dq[i].pop_front ();
}

int getSum ()
{
    if (dq[0].empty ()) return 2 * INF;
    int minA = data[dq[0].front ()][0], minB = data[dq[1].front ()][1], minAB = data[dq[2].front ()][2];
    return max (minA + minB, minAB);
}

void solve (int updown)
{
    ds::init ();
    events.clear ();
    clearDeque ();
    for (int i=1; i<=N; i++)
    {
        events.push_back ({x[i], -y[i]});
        events.push_back ({x[i] + updown + 1, y[i]});
    }
    sort (events.begin (), events.end ()), nr = 0;
    for (int ii=0; ii<events.size (); ii++)
    {
        int jj = ii;
        while (jj < events.size () && events[jj].first == events[ii].first)
        {
            if (events[jj].second < 0) ds::add (-events[jj].second);
            else ds::del (events[jj].second);
            jj ++;
        }
        jj --;
        ///[ii, jj]
        nr ++, pos[nr] = events[ii].first;
        data[nr][0] = ds::getA ();
        data[nr][1] = ds::getB ();
        data[nr][2] = ds::maxDif () - 1;
        ///
        ii = jj;
    }
    ///we want [i, j] so that pos[j + 1] - pos[i - 1] - 1 >= updown
    ///and max (max (data[k][0]) + max (data[k][1]), max (data[k][2])) is minimal for i<=k<=j
    pos[nr + 1] = pos[nr] - 1, pos[0] = pos[1] - 1;
    int i = 1;
    /*printf ("%d ->\n", updown);
    for (int i=1; i<=nr; i++)
        printf ("%7lld %7d %7d %7d\n", pos[i], data[i][0], data[i][1], data[i][2]);*/
    for (int j=1; j<=nr; j++)
    {
        add (j);
        while (pos[j + 1] - pos[i] - 1 >= R)
            del (i), i ++;
        if (pos[j + 1] - pos[i - 1] - 1 >= R)
        {
            long long curr = updown + getSum ();
            if (curr < ans)
                ans = curr;
        }
    }
}

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

scanf ("%d %d\n", &R, &C);
scanf ("%d", &N);
for (int i=1; i<=N; i++)
    scanf ("%d %d", &x[i], &y[i]);
for (int i=1; i<=N; i++)
    sa.insert (x[i] - 1), sb.insert (R - 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)
    solve (ab);
printf ("%lld\n", ans);
return 0;
}

Compilation message

cultivation.cpp: In function 'void add(int)':
cultivation.cpp:96:35: error: reference to 'data' is ambiguous
         while (!dq[i].empty () && data[dq[i].back ()][i] <= data[pos][i])
                                   ^~~~
cultivation.cpp:81:9: note: candidates are: int data [1209][3]
 int nr, data[1209][3];
         ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from cultivation.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
cultivation.cpp:96:61: error: reference to 'data' is ambiguous
         while (!dq[i].empty () && data[dq[i].back ()][i] <= data[pos][i])
                                                             ^~~~
cultivation.cpp:81:9: note: candidates are: int data [1209][3]
 int nr, data[1209][3];
         ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from cultivation.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
cultivation.cpp: In function 'int getSum()':
cultivation.cpp:112:16: error: reference to 'data' is ambiguous
     int minA = data[dq[0].front ()][0], minB = data[dq[1].front ()][1], minAB = data[dq[2].front ()][2];
                ^~~~
cultivation.cpp:81:9: note: candidates are: int data [1209][3]
 int nr, data[1209][3];
         ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from cultivation.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
cultivation.cpp:113:24: error: 'minB' was not declared in this scope
     return max (minA + minB, minAB);
                        ^~~~
cultivation.cpp:113:24: note: suggested alternative: 'minA'
     return max (minA + minB, minAB);
                        ^~~~
                        minA
cultivation.cpp:113:30: error: 'minAB' was not declared in this scope
     return max (minA + minB, minAB);
                              ^~~~~
cultivation.cpp:113:30: note: suggested alternative: 'minA'
     return max (minA + minB, minAB);
                              ^~~~~
                              minA
cultivation.cpp: In function 'void solve(int)':
cultivation.cpp:127:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii=0; ii<events.size (); ii++)
                    ~~^~~~~~~~~~~~~~~
cultivation.cpp:130:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (jj < events.size () && events[jj].first == events[ii].first)
                ~~~^~~~~~~~~~~~~~~~
cultivation.cpp:139:9: error: reference to 'data' is ambiguous
         data[nr][0] = ds::getA ();
         ^~~~
cultivation.cpp:81:9: note: candidates are: int data [1209][3]
 int nr, data[1209][3];
         ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from cultivation.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
cultivation.cpp:140:9: error: reference to 'data' is ambiguous
         data[nr][1] = ds::getB ();
         ^~~~
cultivation.cpp:81:9: note: candidates are: int data [1209][3]
 int nr, data[1209][3];
         ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from cultivation.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
cultivation.cpp:141:9: error: reference to 'data' is ambiguous
         data[nr][2] = ds::maxDif () - 1;
         ^~~~
cultivation.cpp:81:9: note: candidates are: int data [1209][3]
 int nr, data[1209][3];
         ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from cultivation.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:171:7: 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:172:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
 ~~~~~~^~~~~~~~~~
cultivation.cpp:174:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x[i], &y[i]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~