Submission #92657

#	Time	Username	Problem	Language	Result	Execution time	Memory
92657		SamAnd	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	932 ms	22752 KiB

burrow

#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
#define m_p make_pair
const int N = 1003;

int p[N], ch[N];
int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}

void kpc(int x, int y)
{
    x = fi(x);
    y = fi(y);
    if (ch[x] > ch[y])
    {
        ch[x] += ch[y];
        p[y] = x;
    }
    else
    {
        ch[y] += ch[x];
        p[x] = y;
    }
}

bool c[N];
int tt;
int t[N];

void ubd(int x)
{
    if (c[x - 1] && c[x + 1])
    {
        int tv = t[fi(x - 1)] + t[fi(x + 1)] + 1;
        kpc(x - 1, x);
        kpc(x, x + 1);
        t[fi(x)] = tv;
        tt = max(tt, tv);
    }
    else if (c[x - 1])
    {
        int tv = t[fi(x - 1)] + 1;
        kpc(x - 1, x);
        t[fi(x)] = tv;
        tt = max(tt, tv);
    }
    else if (c[x + 1])
    {
        int tv = t[fi(x + 1)] + 1;
        kpc(x, x + 1);
        t[fi(x)] = tv;
        tt = max(tt, tv);
    }
    else
    {
        int tv = 1;
        t[fi(x)] = tv;
        tt = max(tt, tv);
    }
    c[x] = true;
}

int n, m, k;
int a[N][N];

void clr()
{
    for (int i = 1; i <= m; ++i)
    {
        c[i] = false;
        p[i] = i;
        ch[i] = 1;
        t[i] = 0;
    }
    tt = 0;
}

queue<int> q[N];

int xx[N][N];
int stg(int x)
{
    for (int j = 1; j <= m; ++j)
    {
        if (a[n][j] < x)
            xx[n][j] = n;
        else
            xx[n][j] = N;
        for (int i = n - 1; i >= 1; --i)
        {
            if (a[i][j] < x)
                xx[i][j] = i;
            else
                xx[i][j] = xx[i + 1][j];
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        clr();
        for (int j = 1; j <= m; ++j)
        {
            if (xx[i][j] == N)
                ubd(j);
            else
            {
                if (xx[i][j] != i)
                    q[xx[i][j]].push(j);
            }
        }

        for (int ii = n; ii >= i; --ii)
        {
            while (!q[ii + 1].empty())
            {
                ubd(q[ii + 1].front());
                q[ii + 1].pop();
            }
            ans = max(ans, (ii - i + 1) * tt);
        }
    }
    return ans;
}

vector<int> v;
int main()
{
    //freopen("input2.txt", "r", stdin);
    //freopen("minimum.in", "r", stdin);
    //freopen("minimum.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            scanf("%d", &a[i][j]);
            v.push_back(a[i][j]);
        }
    }
    sort(v.begin(), v.end());
    int l = 0, r = v.size() - 1;
    while ((r - l) > 4)
    {
        int m = v[(l + r) / 2];
        if (stg(m) >= k)
            l = (l + r) / 2;
        else
            r = (l + r) / 2;
    }
    for (int i = r; i >= l; --i)
    {
        int m = v[i];
        if (stg(m) >= k)
        {
            cout << m << " " << stg(m) << endl;
            return 0;
        }
    }
    return 0;
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:145:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100