【codeforces 548B】Mike and Fun
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Mike and some bears are playing a game just for fun. Mike is the judge. All bears except Mike are standing in an n × m grid, there’s exactly one bear in each cell. We denote the bear standing in column number j of row number i by (i, j). Mike’s hands are on his ears (since he’s the judge) and each bear standing in the grid has hands either on his mouth or his eyes.
They play for q rounds. In each round, Mike chooses a bear (i, j) and tells him to change his state i. e. if his hands are on his mouth, then he’ll put his hands on his eyes or he’ll put his hands on his mouth otherwise. After that, Mike wants to know the score of the bears.
Score of the bears is the maximum over all rows of number of consecutive bears with hands on their eyes in that row.
Since bears are lazy, Mike asked you for help. For each round, tell him the score of these bears after changing the state of a bear selected in that round.
Input
The first line of input contains three integers n, m and q (1 ≤ n, m ≤ 500 and 1 ≤ q ≤ 5000).
The next n lines contain the grid description. There are m integers separated by spaces in each line. Each of these numbers is either 0 (for mouth) or 1 (for eyes).
The next q lines contain the information about the rounds. Each of them contains two integers i and j (1 ≤ i ≤ n and 1 ≤ j ≤ m), the row number and the column number of the bear changing his state.
Output
After each round, print the current score of the bears.
Examples
input
5 4 5
0 1 1 0
1 0 0 1
0 1 1 0
1 0 0 1
0 0 0 0
1 1
1 4
1 1
4 2
4 3
output
3
4
3
3
4
【题目链接】:http://codeforces.com/contest/548/problem/B
【题解】
思路挺简单的;
就是先算出每一行的答案;存在ans[maxn]里面;
(然后把这maxn个答案存在set里面->结构体记录id);
然后每次更新只会影响这一行的答案。
所以更新一个点之后用O(N)更新这一行的答案.在set中把这一行原来的答案去掉,然后把新的答案加到set里面.
每次结束后输出最大值就好了。
复杂度就O(N*Q*lo2gn)左右吧;
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 500+10;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
struct abc
{
int num,id;
friend bool operator < (abc a,abc b)
{
if (a.num != b.num)
return a.num > b.num;
else
return a.id < b.id;
}
};
int n,m,q,ans[MAXN];
int a[MAXN][MAXN];
set <abc> myset;
int main()
{
//freopen("F:\\rush.txt","r",stdin);
rei(n);rei(m);rei(q);
rep1(i,1,n)
rep1(j,1,m)
rei(a[i][j]);
rep1(i,1,n)
{
int le = 0;
rep1(j,1,m)
if (a[i][j]==1)
{
int r = j;
while (r+1<=m && a[i][r+1]==1)
r++;
int temp = r-j+1;
if (temp > le)
le = temp;
}
ans[i] = le;
myset.insert({le,i});
}
rep1(i,1,q)
{
int x,y;
rei(x);rei(y);
a[x][y] = 1-a[x][y];
int le = 0;
rep1(j,1,m)
if (a[x][j]==1)
{
int r = j;
while (r+1<=m && a[x][r+1]==1)
r++;
int temp = r-j+1;
if (temp > le)
le = temp;
}
myset.erase({ans[x],x});
ans[x] = le;
myset.insert({ans[x],x});
printf("%d\n",myset.begin()->num);
}
return 0;
}
相关文章
- [XState] Parallel State and deep history state
- [Cypress] install, configure, and script Cypress for JavaScript web applications -- part3
- [Cypress] install, configure, and script Cypress for JavaScript web applications -- part1
- [RxJS] Implement pause and resume feature correctly through RxJS
- SAP ui5 control lifecycle - registration and deregistration
- 【Codeforces 584D】Dima and Lisa
- 【ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) A】 Palindromic Supersequence
- 【非常高%】【codeforces 733A】Grasshopper And the String
- 【50.49%】【codeforces 731B】Coupons and Discounts
- 【codeforces 768C】Jon Snow and his Favourite Number
- 【codeforces 760C】Pavel and barbecue
- 【codeforces 750E】New Year and Old Subsequence
- 【codeforces 546D】Soldier and Number Game
- 【codeforces 752F】Santa Clauses and a Soccer Championship
- 【codeforces 510B】Fox And Two Dots
- 【codeforces 514C】Watto and Mechanism(字典树做法)
- 【Codeforces Round #420 (Div. 2) A】Okabe and Future Gadget Laboratory
- 【codeforces 255D】Mr. Bender and Square
- Unexpected XML declaration. The XML declaration must be the first node in the document and no white
- 成功解决matplotlibaxes_axes.py:6462: UserWarning: The 'normed' kwarg is deprecated, and has been repla
- Codeforces 385 C Bear and Prime Numbers
- Using Qt to build an Omi App for iOS (and Android)
- 论文解读(GSAT)《Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism》
- Codeforces Round #311 (Div. 2)A Ilya and Diplomas