oj.uz

Submission #392351

# Submission time Handle Problem Language Result Execution time Memory
392351 2021-04-20T20:19:34 Z lukameladze Furniture (JOI20_furniture) C++14
100 / 100
 2393 ms 43556 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int   N=1005;
long long n,m,fix[3][N][N],x,y,a,b,aa[N][N],mp[3*N],r[N][N],qq,xx,yy;
queue< pair <int ,int > > q;
int check1(int x, int y) {
     if((y==1 ||r[x][y-1]==1) && (x==1 || r[x-1][y]==1)) 
     return 1;
     else return 0;
}
int check2(int x, int y) {
     if((y==m ||r[x][y+1]==1) && (x==n || r[x+1][y]==1)) 
     return 1;
     else return 0;
}
int check(int x, int y) {
     if (x>n || y>m || x<1 || y<1) return 0;
     else return 1;
}
void go(int a, int b, int ty) {
     if (fix[ty+1][a][b]==1) return;
     fix[ty+1][a][b]=1;
     if (check(a+ty,b) && aa[a+ty][b]==0) go(a+ty,b,ty);
     if (check(a,ty+b) && aa[a][ty+b]==0 ) go(a,ty+b,ty);
}
 
void update1(int a, int b) {
     while(!q.empty())
     q.pop();
     x=a;
     y=b;
     if (r[x+1][y]!=1 && check(x+1, y) && check1(x+1,y)) {
          q.push({x+1,y});
       //   r[x+1][y]=1;
         // mp[x+y+1]--;
     }
     if (r[x][y+1]!=1 && check(x, y+1) && check1(x,y+1)) {
          q.push({x,y+1});
     //     r[x][y+1]=1;
       //   mp[x+y+1]--;
     }
     while (!q.empty()) {
          x=q.front().f;
          y=q.front().s;
          q.pop();
          if (r[x][y] || !check1(x,y)) continue;
          r[x][y]=1;
          mp[x+y]--;
          if (check(x+1, y)) {
               q.push({x+1,y});
          }
          if (check(x, y+1)) {
               q.push({x,y+1});
          }
     }
}
 
void update2(int a, int b) {
     while(!q.empty())
     q.pop();
     x=a;
     y=b;
     if (r[x-1][y]!=1 && check(x-1, y) && check2(x-1,y)) {
          q.push({x-1,y});
///          r[x-1][y]=1;
   //       mp[x+y-1]--;
     }
     if (r[x][y-1]!=1 && check(x, y-1) && check2(x,y-1)) {
          q.push({x,y-1});
     //     r[x][y-1]=1;
       //   mp[x+y-1]--;
     }
     while (!q.empty()) {
          x=q.front().f;
          y=q.front().s;
          q.pop();
          if (r[x][y] || !check2(x,y)) continue;
          r[x][y]=1;
          mp[x+y]--;
          if (check(x-1, y)) {
               q.push({x-1,y});
          }
          if (check(x, y-1)) {
               q.push({x,y-1});
          }
     }
}
int main() {
     cin>>n>>m;
     for (int i=1; i<=n; i++) {
          for (int j=1; j<=m; j++) {
               cin>>aa[i][j];
          }
     }
     go(1,1,1);
     go(n,m,-1);
     for (int i=1; i<=n; i++) {
          for (int j=1; j<=m; j++) {
               if (fix[0][i][j] && fix[2][i][j]) {
                    r[i][j]=0;
                    mp[i+j]++;
               } else r[i][j]=1;
          }
     }
      cin>>qq;
     for (int i=1; i<=qq; i++) {
          cin>>xx>>yy;
          if (r[xx][yy]==1) {
               cout<<1<<endl;
               continue;
          }
          if (mp[xx+yy]==1) {
               cout<<0<<endl;
               continue;
          }
          cout<<1<<endl;
          mp[xx+yy]--;
          r[xx][yy]=1;
          update1(xx,yy);
          update2(xx,yy);
     }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 11 ms 1996 KB Output is correct
4 Correct 19 ms 2188 KB Output is correct
5 Correct 20 ms 2304 KB Output is correct
6 Correct 24 ms 2232 KB Output is correct
7 Correct 24 ms 2252 KB Output is correct
8 Correct 23 ms 2252 KB Output is correct
9 Correct 24 ms 2340 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 11 ms 1996 KB Output is correct
4 Correct 19 ms 2188 KB Output is correct
5 Correct 20 ms 2304 KB Output is correct
6 Correct 24 ms 2232 KB Output is correct
7 Correct 24 ms 2252 KB Output is correct
8 Correct 23 ms 2252 KB Output is correct
9 Correct 24 ms 2340 KB Output is correct
10 Correct 59 ms 2364 KB Output is correct
11 Correct 15 ms 1504 KB Output is correct
12 Correct 861 ms 36212 KB Output is correct
13 Correct 211 ms 32016 KB Output is correct
14 Correct 1933 ms 39268 KB Output is correct
15 Correct 2039 ms 39396 KB Output is correct
16 Correct 2153 ms 40936 KB Output is correct
17 Correct 2306 ms 42984 KB Output is correct
18 Correct 2271 ms 42064 KB Output is correct
19 Correct 2360 ms 43460 KB Output is correct
20 Correct 2317 ms 43556 KB Output is correct
21 Correct 2393 ms 43524 KB Output is correct