oj.uz

Submission #47038

# Submission time Handle Problem Language Result Execution time Memory
47038 2018-04-26T15:59:31 Z SpaimaCarpatilor Cultivation (JOI17_cultivation) C++17
0 / 100
 34 ms 576 KB 
#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 INF;
        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 ());
    }
}

vector < pair < int, int > > events;
void solve (int up, int down)
{
    int minA = 0, minB = 0, minAB = 0;
    ds::init ();
    events.clear ();
    for (int i=1; i<=N; i++)
    {
        int lx = max (1, x[i] - up), dx = min (R, x[i] + down);
        events.push_back ({lx, -y[i]});
        if (dx + 1 <= R)
            events.push_back ({dx + 1, y[i]});
    }
    sort (events.begin (), events.end ());
    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]
        minA = max (minA, ds::getA ());
        minB = max (minB, ds::getB ());
        minAB = max (minAB, ds::maxDif () - 1);
        ///
        ii = jj;
    }
//    printf ("(%d, %d) -> (%d, %d, %d)\n", up, down, minA, minB, minAB);
    long long curr = (long long) max (minA + minB, minAB) + up + down;
    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)
{
    set < int > psb;
    for (auto b : sb)
        psb.insert (b);
    for (auto ab : sab)
        if (ab >= a)
            psb.insert (ab - a);
    for (auto b : psb)
        solve (a, b);
}
printf ("%lld\n", ans);
return 0;
}

Compilation message

cultivation.cpp: In function 'void solve(int, int)':
cultivation.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii=0; ii<events.size (); ii++)
                    ~~^~~~~~~~~~~~~~~
cultivation.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (jj < events.size () && events[jj].first == events[ii].first)
                ~~~^~~~~~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:122: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:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
 ~~~~~~^~~~~~~~~~
cultivation.cpp:125: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]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 420 KB Output is correct
2 Correct 30 ms 432 KB Output is correct
3 Correct 33 ms 572 KB Output is correct
4 Correct 25 ms 572 KB Output is correct
5 Correct 34 ms 572 KB Output is correct
6 Correct 17 ms 572 KB Output is correct
7 Correct 4 ms 572 KB Output is correct
8 Incorrect 15 ms 576 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 420 KB Output is correct
2 Correct 30 ms 432 KB Output is correct
3 Correct 33 ms 572 KB Output is correct
4 Correct 25 ms 572 KB Output is correct
5 Correct 34 ms 572 KB Output is correct
6 Correct 17 ms 572 KB Output is correct
7 Correct 4 ms 572 KB Output is correct
8 Incorrect 15 ms 576 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -