제출 #164219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164219		Alexa2001	Rectangles (IOI19_rect)	C++17	100 / 100	2122 ms	333576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Nmax = 2505;

int go_up[Nmax][Nmax], go_down[Nmax][Nmax], go_left[Nmax][Nmax], go_right[Nmax][Nmax], h[Nmax][Nmax];
int dp_up[Nmax][Nmax], dp_down[Nmax][Nmax], dp_left[Nmax][Nmax], dp_right[Nmax][Nmax];

int n, m;
vector<int> pos[Nmax];


static void compute(vector<int> &v, vector<int> &go)
{
    go.resize(v.size());

    int i, nr = 0;
    vector<int> st(v.size() + 1);
    st[0] = -1;

    for(i=0; i<v.size(); ++i)
    {
        while(nr && v[i] > v[st[nr]]) --nr;
        go[i] = st[nr];
        st[++nr] = i;
    }
}

static void prec()
{
    vector<int> aux, ans;
    int i, j;

    for(i=0; i<n; ++i)
    {
        aux.clear();
        for(j=0; j<m; ++j) aux.push_back(h[i][j]);
        compute(aux, ans);

        for(j=0; j<m; ++j)
            go_left[i][j] = ans[j];

        reverse(aux.begin(), aux.end());
        compute(aux, ans);

        for(j=0; j<m; ++j)
            go_right[i][j] = m-1-ans[m-j-1];
    }

    for(j=0; j<m; ++j)
    {
        aux.clear();
        for(i=0; i<n; ++i) aux.push_back(h[i][j]);
        compute(aux, ans);

        for(i=0; i<n; ++i)
            go_up[i][j] = ans[i];

        reverse(aux.begin(), aux.end());
        compute(aux, ans);

        for(i=0; i<n; ++i)
            go_down[i][j] = n-1-ans[n-i-1];
    }
}

static void prec2()
{
    int i, j;

    for(j=m-1; j>=0; --j)
        for(i=n-1; i>=0; --i)
        {
            if(j<m-1 && go_down[i][j+1] == go_down[i][j])
                dp_down[i][j] = 1 + dp_down[i][j+1];
            else if(j<m-1 && go_up[go_down[i][j]][j+1] == i) dp_down[i][j] = 1 + dp_up[go_down[i][j]][j+1];
            else dp_down[i][j] = 1;

            ///

            if(j<m-1 && go_up[i][j+1] == go_up[i][j])
                dp_up[i][j] = 1 + dp_up[i][j+1];
            else if(j<m-1 && go_down[go_up[i][j]][j+1] == i) dp_up[i][j] = 1 + dp_down[go_up[i][j]][j+1];
            else dp_up[i][j] = 1;
        }

    for(i=n-1; i>=0; --i)
        for(j=m-1; j>=0; --j)
        {
            ///

            if(i<n-1 && go_right[i+1][j] == go_right[i][j])
                dp_right[i][j] = 1 + dp_right[i+1][j];
            else if(i<n-1 && go_left[i+1][go_right[i][j]] == j) dp_right[i][j] = 1 + dp_left[i+1][go_right[i][j]];
            else dp_right[i][j] = 1;

            ///

            if(i<n-1 && go_left[i+1][j] == go_left[i][j])
                dp_left[i][j] = 1 + dp_left[i+1][j];
            else if(i<n-1 && go_right[i+1][go_left[i][j]] == j) dp_left[i][j] = 1 + dp_right[i+1][go_left[i][j]];
            else dp_left[i][j] = 1;
        }
}

static bool check(int x, int y, int n, int m)
{
    if(!n || !m) return 0;

   // cerr << "candidate: cell " << x << ' ' << y << " dim " << n << ' ' << m << '\n';

    /// coltul stanga-sus in (x, y), dimensiune (n, m)

    bool ok = 1;

    if(go_down[x-1][y] == x+n)
        ok &= (dp_down[x-1][y] >= m);
    else if(go_up[x+n][y] == x-1) ok &= (dp_up[x+n][y] >= m);
        else ok = 0;

    if(go_right[x][y-1] == y+m)
        ok &= (dp_right[x][y-1] >= n);
    else if(go_left[x][y+m] == y-1) ok &= (dp_left[x][y+m] >= n);
        else ok = 0;

   // cerr << "answer: " << (int) ok << '\n';

  //  if(ok) cerr << "# " << "candidate: cell " << x << ' ' << y << " dim " << n << ' ' << m << '\n';

    return ok;
}

ll solve()
{
    int i, j;
    int ans = 0;

    for(i=1; i<n-1; ++i)
    {
        for(j=0; j<=m; ++j) pos[j].clear(); /// pos[j].shrink_to_fit();

        for(j=0; j<m; ++j)
        {
            if(go_right[i][j] != m)
                pos[j+1].push_back(go_right[i][j] - j - 1);

            if(go_left[i][j] != -1 && h[i][j] != h[i][go_left[i][j]])
                pos[go_left[i][j] + 1].push_back(j - go_left[i][j] - 1);
        }

        for(j=1; j<m-1; ++j)
        {
            if(go_down[i-1][j] == n) continue;

            int N;
            N = go_down[i-1][j] - i;

            for(auto M : pos[j])
                ans += check(i, j, N, M);
        }

        for(j=m-2; j>=1; --j)
        {
            if(go_up[i+1][j] == -1) continue;
            if(h[i+1][j] == h[go_up[i+1][j]][j]) continue;

            int N;
            N = i - go_up[i+1][j];

            for(auto M : pos[j])
                ans += check(i-N+1, j, N, M);
        }
    }

    return ans;
}

ll count_rectangles(vector<vector<int>> _h)
{
    n = _h.size();
    m = _h[0].size();

    int i, j;
    for(i=0; i<n; ++i)
        for(j=0; j<m; ++j)
            h[i][j] = _h[i][j];

    prec();
    prec2();
    return solve();
}

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

rect.cpp: In function 'void compute(std::vector<int>&, std::vector<int>&)':
rect.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); ++i)
              ~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28