oj.uz

Submission #392354

# Submission time Handle Problem Language Result Execution time Memory
392354 2021-04-20T20:25:51 Z lukameladze Furniture (JOI20_furniture) C++14
100 / 100
 2347 ms 34116 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 9 ms 2056 KB Output is correct
3 Correct 11 ms 1996 KB Output is correct
4 Correct 18 ms 2208 KB Output is correct
5 Correct 21 ms 2252 KB Output is correct
6 Correct 24 ms 2344 KB Output is correct
7 Correct 24 ms 2368 KB Output is correct
8 Correct 23 ms 2340 KB Output is correct
9 Correct 31 ms 2344 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 9 ms 2056 KB Output is correct
3 Correct 11 ms 1996 KB Output is correct
4 Correct 18 ms 2208 KB Output is correct
5 Correct 21 ms 2252 KB Output is correct
6 Correct 24 ms 2344 KB Output is correct
7 Correct 24 ms 2368 KB Output is correct
8 Correct 23 ms 2340 KB Output is correct
9 Correct 31 ms 2344 KB Output is correct
10 Correct 59 ms 2380 KB Output is correct
11 Correct 16 ms 1484 KB Output is correct
12 Correct 872 ms 32168 KB Output is correct
13 Correct 205 ms 30440 KB Output is correct
14 Correct 2090 ms 31524 KB Output is correct
15 Correct 2126 ms 31592 KB Output is correct
16 Correct 2206 ms 32300 KB Output is correct
17 Correct 2294 ms 33888 KB Output is correct
18 Correct 2218 ms 32868 KB Output is correct
19 Correct 2347 ms 34116 KB Output is correct
20 Correct 2269 ms 34116 KB Output is correct
21 Correct 2337 ms 34088 KB Output is correct