#include<bits/stdc++.h>
#define st first
#define nd second
#define eb emplace_back
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){cerr<<h;if(sizeof...(t))cerr<<", ";debug(t...);};
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1e3+5, INF=1e9+5;
set<int> S[N];
int dp[N], dp2[N];
int main(){
//ios_base::sync_with_stdio(0);cin.tie(0);
int n, m;
cin>>n>>m;
for(int i=1; i<=n; i++){
S[i].insert(m+1);
if(i!=1)S[i].insert(0);
for(int j=1; j<=m; j++){
int x;
cin>>x;
if(x)S[i].insert(j);
}
}
dp[0]=1;
for(int i=1; i<=n; i++){
auto it=S[i].lower_bound(dp[i-1]-1);
dp[i]=*it;
}
dp2[n]=m;
for(int i=n-1; i>0; i--){
auto it=S[i+1].upper_bound(dp2[i+1]);
it--;
dp2[i]=1+*it;
}
int q;
cin>>q;
while(q--){
/*for(int i=1; i<=n; i++){
deb(dp[i], dp2[i]);
}*/
int x, y;
cin>>x>>y;
if(y>dp2[x] || y<dp[x-1]-1){
cout<<1<<"\n";
S[x].insert(y);
for(int i=x; i<=n; i++){
auto it=S[i].lower_bound(dp[i-1]-1);
if(dp[i]==*it)break;
dp[i]=*it;
}
for(int i=x-1; i>0; i--){
auto it=S[i+1].upper_bound(dp2[i+1]);
it--;
if(dp2[i]==1+*it)break;
dp2[i]=1+*it;
}
}
else{
cout<<0<<"\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
