oj.uz

Submission #715981

# Submission time Handle Problem Language Result Execution time Memory
715981 2023-03-28T16:33:34 Z KiaRez Furniture (JOI20_furniture) C++17
100 / 100
 312 ms 18932 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int N = 1005, lg=18;
const ll MOD = 1e9+7; // 998244353

ll getmod(ll a, ll mod=MOD)                   {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}
inline ll poww(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = getmod(ans*a);
        b >>= 1;
        a = getmod(a*a);
    }
    return ans;
}

int n, m, q, A[N][N], cnt[N], dp[N][N], pd[N][N], mark[N][N], OK[N][N];
int dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
int main () {
	ios;

	cin>>n>>m;
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			cin>>mark[i][j];
		}
	}
	for(int i=0;i<N;++i) {
		mark[n+1][i]=mark[0][i]=mark[i][m+1]=mark[i][0]=1;
	}

	pd[n][m]=dp[1][1]=1;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j){
			dp[i][j]|=(dp[i-1][j] && mark[i-1][j]==0 && mark[i][j]==0);
			dp[i][j]|=(dp[i][j-1] && mark[i][j-1]==0 && mark[i][j]==0);
		}
	}
	for(int i=n;i;--i) {
		for(int j=m;j;--j){
			pd[i][j]|=(pd[i+1][j] && mark[i+1][j]==0 && mark[i][j]==0);
			pd[i][j]|=(pd[i][j+1] && mark[i][j+1]==0 && mark[i][j]==0);
			if(pd[i][j] == dp[i][j] && pd[i][j] == 1) {
				OK[i][j]=1;
				cnt[i+j]++;
			}
		}
	}

	cin>>q;
	while(q--) {
		int x,y;
		cin>>x>>y;
		if(OK[x][y] == 0) {
			mark[x][y]=1;
			cout<<"1\n";
			continue;
		}
		if(cnt[x+y]==1) {
			cout<<"0\n";
			continue;
		}
		cout<<"1\n";
		mark[x][y]=1;
		queue<pii> q;
		q.push({x, y});
		while(!q.empty()) {
			pii v = q.front();
			q.pop();
			cnt[v.F+v.S]--;
			dp[v.F][v.S] = pd[v.F][v.S] = OK[v.F][v.S] = 0;
			for(int i=0;i<4;++i) {
				int a=v.F+dx[i], b=v.S+dy[i];
				if(Mp(a,b)==Mp(1,1) || Mp(a,b)==Mp(n,m)) {
					continue;
				}
				if(mark[a][b]==0 && OK[a][b]==1 && ((dp[a-1][b]==0&&dp[a][b-1]==0) || (pd[a+1][b]==0&&pd[a][b+1]==0))) {
					dp[a][b]=pd[a][b]=OK[a][b]=0;
					q.push({a,b});
				}
			}
		}
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 4 ms 5328 KB Output is correct
4 Correct 4 ms 5456 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5588 KB Output is correct
9 Correct 5 ms 5460 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 4 ms 5328 KB Output is correct
4 Correct 4 ms 5456 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5588 KB Output is correct
9 Correct 5 ms 5460 KB Output is correct
10 Correct 9 ms 5460 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 207 ms 17456 KB Output is correct
13 Correct 75 ms 16464 KB Output is correct
14 Correct 290 ms 17792 KB Output is correct
15 Correct 291 ms 17932 KB Output is correct
16 Correct 291 ms 18160 KB Output is correct
17 Correct 309 ms 18924 KB Output is correct
18 Correct 310 ms 18460 KB Output is correct
19 Correct 298 ms 18896 KB Output is correct
20 Correct 231 ms 18892 KB Output is correct
21 Correct 312 ms 18932 KB Output is correct