Codeforces Round #248 (Div. 1)??Nanami's Digital Board_html/css

Codeforces Round #248 (Div. 1)??Nanami's Digital Board_html/css_WEB-ITnose

WBOY

Release： 2016-06-24 12:01:49

Original

1199 people have browsed it

Question connection

Question meaning:
Given an n*m 0/1 matrix, q operations, each time there are two types: 1) Change x , flip the y position value 2) Calculate the maximum area of the rectangle bounded by (x, y)
(1?≤?n,?m,?q?≤?1000)

Analysis:
Consider the case where (x, y) is the lower boundary, h = the maximum number of consecutive 1's above (x, y). Then for the descending enumeration, for the current hx, you only need to look at the farthest distance that can be reached on both sides, so that h (x, ty) is not greater than h. The distance on both sides obtained by the subsequent enumeration is greater than or equal to the previous one, so just continue the enumeration with the previous distance on both sides.

const int maxn = 1100;int n, m, q;int ipt[maxn][maxn];int up[maxn][maxn], dwn[maxn][maxn], lft[maxn][maxn], rht[maxn][maxn];int len[maxn];void updaterow(int r){    FE(j, 1, m)        lft[r][j] = (ipt[r][j] == 1 ? lft[r][j - 1] + 1 : 0);    FED(j, m, 1)        rht[r][j] = (ipt[r][j] == 1 ? rht[r][j + 1] + 1 : 0);}void updatecol(int c){    FE(i, 1, n)        up[i][c] = (ipt[i][c] == 1 ? up[i - 1][c] + 1 : 0);    FED(i, n, 1)        dwn[i][c] = (ipt[i][c] == 1 ? dwn[i + 1][c] + 1 : 0);}int maxarea(int s, int len[], int thes){    int l = s, r = s, ret = 0;    FED(i, len[s], 1)    {        while (l >= 1 && len[l] >= i)            l--;        while (r <= thes && len[r] >= i)            r++;        ret = max(ret, i * (r - l - 1));    }    return ret;}int main(){    while (~RIII(n, m, q))    {        FE(i, 1, n) FE(j, 1, m)            RI(ipt[i][j]);        FE(i, 1, n)            updaterow(i);        FE(j, 1, m)            updatecol(j);        REP(kase, q)        {            int op, x, y;            RIII(op, x, y);            if (op == 1)            {                ipt[x][y] ^= 1;                updatecol(y);                updaterow(x);            }            else            {                int ans = max(maxarea(y, up[x], m), maxarea(y, dwn[x], m));                FE(i, 1, n)                    len[i] = lft[i][y];                ans = max(ans, maxarea(x, len, n));                FE(i, 1, n)                    len[i] = rht[i][y];                ans = max(ans, maxarea(x, len, n));                WI(ans);            }        }    }    return 0;}

Copy after login