Submission #392351

#	Time	Username	Problem	Language	Result	Execution time	Memory
392351		lukameladze	Furniture (JOI20_furniture)	C++14	100 / 100	2393 ms	43556 KiB

furniture

# 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 / 5
• Subtask 2: 95 / 95