제출 #582966

#제출 시각아이디문제언어결과실행 시간메모리
582966Theo830Furniture (JOI20_furniture)C++17
0 / 100
813 ms524288 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ll,ii> #define ull unsigned ll #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training template <typename T> struct Bit{ int N; vector<T>bit; void build(ll n){ N = n+5; f(i,0,N){ bit.pb(0); } } void upd(ll k,T x){ k++; while(k < N){ bit[k] += x; k += k & -k; } } T query(ll k){ k++; T ans = 0; while(k >= 1){ ans += bit[k]; k -= k & -k; } return ans; } }; int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); ll n,m; cin>>n>>m; char arr[n][m]; bool exo[n][m][3]; f(i,0,n){ f(j,0,m){ cin>>arr[i][j]; } } f(i,0,n){ f(j,0,m){ if(i == 0 && j == 0){ exo[i][j][0] = true; } else if(arr[i][j] == '1'){ exo[i][j][0] = false; } else if(i == 0){ exo[i][j][0] = exo[i][j-1][0]; } else if(j == 0){ exo[i][j][0] = exo[i-1][j][0]; } else{ exo[i][j][0] = exo[i-1][j][0] | exo[i][j-1][0]; } } } for(ll i = n-1;i >= 0;i--){ for(ll j = m-1;j >= 0;j--){ if(i == n-1 && j == m-1){ exo[i][j][1] = true; } else if(arr[i][j] == '1'){ exo[i][j][1] = false; } else if(i == n-1){ exo[i][j][1] = exo[i][j+1][1]; } else if(j == m-1){ exo[i][j][1] = exo[i+1][j][1]; } else{ exo[i][j][1] = exo[i+1][j][1] | exo[i][j+1][1]; } } } Bit<ll> ex1[n+5]; Bit<ll> ex2[m+5]; f(i,0,n){ ex1[i].build(m + 5); } f(i,0,m){ ex2[i].build(n + 5); } f(i,0,n){ f(j,0,m){ exo[i][j][2] = exo[i][j][0] & exo[i][j][1]; ex1[i].upd(j,exo[i][j][2]); ex2[j].upd(i,exo[i][j][2]); } } ll q; cin>>q; while(q--){ ll a,b; cin>>a>>b; a--; b--; bool ok = 0; if(a > 0){ ok |= (ex1[a - 1].query(m + 1) - ex1[a - 1].query(b)) > 0; } if(b > 0){ ok |= (ex2[b - 1].query(n + 1) - ex2[b - 1].query(a)) > 0; } cout<<ok<<"\n"; if(ok){ exo[a][b][0] = exo[a][b][1] = false; queue<ii>q; q.push(ii(a,b)); vector<ii>ep; while(!q.empty()){ ii f = q.front(); ep.pb(f); q.pop(); ll i = f.F,j = f.S; if(i > 0){ if(j == m-1 || !exo[i-1][j+1][1]){ exo[i-1][j][1] = false; q.push(ii(i-1,j)); } } if(j > 0){ if(i == n-1 || !exo[i+1][j-1][1]){ exo[i][j-1][1] = false; q.push(ii(i,j-1)); } } } q.push(ii(a,b)); while(!q.empty()){ ii f = q.front(); ep.pb(f); q.pop(); ll i = f.F,j = f.S; if(i < n-1){ if(j == 0 || !exo[i+1][j-1][0]){ exo[i+1][j][0] = false; q.push(ii(i+1,j)); } } if(j < m-1){ if(i == 0 || !exo[i-1][j+1][0]){ exo[i][j+1][0] = false; q.push(ii(i,j+1)); } } } for(auto x:ep){ if(exo[x.F][x.S][2]){ exo[x.F][x.S][2] = exo[x.F][x.S][0] & exo[x.F][x.S][1]; if(!exo[x.F][x.S][2]){ ex1[x.F].upd(x.S,-1); ex2[x.S].upd(x.F,-1); } } } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...