#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace std;
//using namespace __gnu_pbds;
//template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN = 1005, base = (1<<10), rozmiar_drzewa = base * 2, INF = 2e9+50;
const ll INF_L = (ll)1e18+(ll)50000;
int n,m,q,y,x;
bool A[MAXN][MAXN];
vector<int> tree[MAXN];
int wsk[MAXN];
set<int> S[MAXN];
int G[MAXN][MAXN];
void update(int i, int v, int val)
{
v += base, tree[i][v] += val, v /= 2;
while(v > 0) tree[i][v] = tree[i][v*2] + tree[i][v*2+1], v /= 2;
}
int query(int i, int l, int p)
{
l = l + base - 1, p = p + base + 1;
int res = 0;
while(l/2 != p/2)
{
if(l % 2 == 0) res += tree[i][l+1];
if(p % 2 == 1) res += tree[i][p-1];
l /= 2, p /= 2;
}
return res;
}
void DFS(int v)
{
if(v == 1) return;
int idx = min(m,wsk[v]+1), kol = -1;
if(*S[v-1].rbegin() <= idx) kol = *S[v-1].rbegin();
auto it = S[v-1].lower_bound(idx);
if(*it > idx) --it;
kol = *it;
if(kol > wsk[v-1]) wsk[v-1] = kol, DFS(v-1);
}
bool dodaj(int y, int x)
{
if(x <= wsk[y]) return 1;
if(n == 1 or m == 1) return 0;
bool stan = 1;
if(y == 1) stan = 0;
else
{
int idx = min(m,x+1), poz = -1;
if(S[y-1].empty()) stan = 1;
else if(*S[y-1].begin() > idx) stan = 1;
else
{
if(*S[y-1].rbegin() <= idx) stan = G[y-1][*S[y-1].rbegin()], poz = *S[y-1].rbegin();
else
{
auto it = S[y-1].lower_bound(idx);
if(*it > idx) --it;
stan = G[y-1][*it], poz = *it;
}
if(stan == 1 and poz != -1)
{
if(poz == m or (m-poz) == query(y-1,m+1,m)) stan = 0;
}
//cout << "YY: " << y << " XX: " << x << " STAN: " << stan << endl;
}
}
//cout << "Y: " << y << " X: " << x << " STAN: " << stan << endl;
G[y][x] = stan;
if(y == n)
{
if(stan == 0) return 0;
else
{
S[y].insert(x), wsk[y] = x, DFS(y);
return 1;
}
}
else
{
if(x > wsk[y+1]+1)
{
S[y].insert(x), update(y,x,1);
return 1;
}
else
{
if(stan == 1)
{
if(x == m or query(y,x+1,m) == m-x) return 0;
else
{
S[y].insert(x), wsk[y] = x, DFS(y), update(y,x,1);
return 1;
}
}
return 0;
}
}
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) cin >> A[i][j];
for(int i = 1; i <= n; ++i) tree[i].assign(rozmiar_drzewa,0), wsk[i] = 0;
for(int i = 1; i <= n; ++i) S[i].insert(0), G[i][0] = 1;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(A[i][j] == 1)
{
bool val = dodaj(i,j);
}
}
}
cin >> q;
while(q--)
{
cin >> y >> x;
bool val = dodaj(y,x);
if(val) cout << "1" << '\n';
else cout << "0" << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
Compilation message
furniture.cpp: In function 'void solve()':
furniture.cpp:136:10: warning: unused variable 'val' [-Wunused-variable]
136 | bool val = dodaj(i,j);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
