oj.uz

Submission #990036

# Submission time Handle Problem Language Result Execution time Memory
990036 2024-05-29T11:45:44 Z AlperenT_ Furniture (JOI20_furniture) C++17
100 / 100
 120 ms 28500 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =2000+10  ,  N = 1e5 +1 , lg = 20 , maxq = 202   , inf = 1e18  , maxk = 2022  , mod =998244353;
int mark[maxn][maxn] , v[maxn] , n, m ;

int ch(int a ,int b){
    if(mark[a-1][b] == 0 && mark[a][b-1] == 0 && (!(a==1 && b==1)))return 1 ;
    if(mark[a+1][b] == 0 && mark[a][b+1] == 0 && (!(a==n&&b==m)))return 1; 
    return 0 ;
}
int dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , -1 , 1}; 

void upd(int x, int y){
    if(mark[x][y] == 0)return ;
    mark[x][y] =0 ;
    v[x+y]--;
    rep(i , 0 , 3){
        int a= x+dx[i] , b = y+dy[i] ;
        if(mark[a][b] == 1 && ch(a,b) == 1){
            upd(a,b) ;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m ;
    vector <pii> vec; 
    rep(i ,1 ,n){
        rep(j ,1 ,m){
            char a ;
            cin >> a;
            if(a=='1')vec.pb({i,j});
            v[i+j] ++ ;
            mark[i][j] = 1 ;
        }
    }
    for(auto [i,j] : vec)upd(i , j);
    int q; 
    cin >> q ;
    while(q--){
        int x, y ;
        cin >> x >> y; 
        if(mark[x][y] == 0){
            cout << "1\n";
            continue ;
        }
        if(v[x+y]==1){
            cout << "0\n";
            continue ;
        }
        upd(x,y) ;
        cout << "1\n";
    }
}

/*

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 4 ms 3164 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 58 ms 22636 KB Output is correct
13 Correct 19 ms 20688 KB Output is correct
14 Correct 120 ms 27340 KB Output is correct
15 Correct 111 ms 26624 KB Output is correct
16 Correct 110 ms 27472 KB Output is correct
17 Correct 115 ms 28240 KB Output is correct
18 Correct 118 ms 27728 KB Output is correct
19 Correct 118 ms 28496 KB Output is correct
20 Correct 112 ms 28496 KB Output is correct
21 Correct 117 ms 28500 KB Output is correct