Home > Web Front-end > HTML Tutorial > codeforces248(div1) B Nanami's Digital Board

codeforces248(div1) B Nanami's Digital Board

PHP中文网
Release: 2017-03-30 17:10:30
Original
1615 people have browsed it

q times of questioning, each query can change a certain value of the matrix (0 to 1, 1 to 0) or query the maximum area of ​​the submatrix, requiring this point to be in the desired submatrix on the boundary of , and all stores in the sub-matrix are 1

Use up[i][j] to represent the longest height that point (i,j) can go upward if (i,j ) is 0, then the value of up[i][j] is 0

Similarly, maintain down,left, rightarray

>

Every time you query, enumerate from up[i][j] to 1 as the height of the submatrix, and then expand to the left and right along the way. If up[i][j - 1] >= up[i][j], you can expand one unit to the left, and the answer is (r - l - 1) * height

Similarly, four Each direction is enumerated separately

//#pragma comment(linker, "/STACK:102400000,102400000")
//HEAD
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>

#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <cstdlib>

using namespace std;
//LOOP
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FED(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
//STL
#define PB push_back
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;


#define FF(i, a, b) for(int i = (a); i < (b); ++i)
#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define EQ(a, b) (fabs((a) - (b)) <= 1e-10)
#define ALL(c) (c).begin(), (c).end()
#define SZ(V) (int)V.size()
#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)
#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)
#define WI(n) printf("%d\n", n)
#define WS(s) printf("%s\n", s)
typedef vector <int> VI;
typedef unsigned long long ULL;
const double eps = 1e-10;
const LL MOD = 1e9 + 7;
const int maxn = 1010;

int ipt[maxn][maxn];
int up[maxn][maxn], dwn[maxn][maxn], rht[maxn][maxn], lft[maxn][maxn];
int len[maxn], n, m;

void update_col(int y)
{
    FE(i, 1, n)
        if (ipt[i][y])
            up[i][y] = up[i - 1][y] + 1;
        else    up[i][y] = 0;
    FED(i, n, 1)
        if (ipt[i][y])
            dwn[i][y] = dwn[i + 1][y] + 1;
        else
            dwn[i][y] = 0;
}

void update_row(int x)
{
    FE(j, 1, m)
        if (ipt[x][j])
            lft[x][j] = lft[x][j - 1] + 1;
        else    lft[x][j] = 0;
    FED(j, m, 1)
        if (ipt[x][j])
            rht[x][j] = rht[x][j + 1] + 1;
        else    rht[x][j] = 0;
}

int solve(int sta, int hei, int con)
{
    int lm = sta, rm = sta;
    int ans = 0;
    for (int h = hei; h >= 1; h--)
    {
        while (lm >= 1 && len[lm] >= h)
            lm--;
        while (rm <= con && len[rm] >= h)
            rm++;
        ans = max(ans, h * (rm - lm - 1));
    }
    return ans;
}

int main()
{
    //freopen("0.txt", "r", stdin);
    int q, x, y, op;
    cin >> n >> m >> q;
    FE(i, 1, n)
        FE(j, 1, m)
            RI(ipt[i][j]);
    FE(i, 1, n)
        update_row(i);
    FE(j, 1, m)
        update_col(j);
    while (q--)
    {
        RIII(op, x, y);
        if (op == 1)
        {
            ipt[x][y] ^= 1;
            update_row(x);
            update_col(y);
//            cout << "UP  " << endl;
//            FE(i, 1, n) {
//                FE(j, 1, m)
//                    cout << up[i][j] << &#39; &#39;;
//                    cout <<endl;
//            }
//            cout << "----" << endl;
//            cout << "right  " << endl;
//            FE(i, 1, n) {
//                FE(j, 1, m)
//                    cout << rht[i][j] << &#39; &#39;;
//                    cout <<endl;
//            }
//            cout << "----" << endl;
        }
        else
        {
            int ans = 0;
            FE(j, 1, m) len[j] = up[x][j];
            ans = max(ans, solve(y, len[y], m));
            FE(j, 1, m) len[j] = dwn[x][j];
            ans = max(ans, solve(y, len[y], m));
            FE(i, 1, n) len[i] = lft[i][y];
            ans = max(ans, solve(x, len[x], n));
            FE(i, 1, n) len[i] = rht[i][y];
            ans = max(ans, solve(x, len[x], n));
            WI(ans);
        }
    }
    return 0;
}
Copy after login

The above is the content of codeforces248(div1) B Nanami's Digital Board. For more related content, please pay attention to the PHP Chinese website (m.sbmmt.com)!


source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template