Submission #392290

#	Time	Username	Problem	Language	Result	Execution time	Memory
392290		lukameladze	Furniture (JOI20_furniture)	C++14	0 / 100	9 ms	1996 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;
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 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();
     q.push({a,b});
     while (!q.empty()) {
          x=q.front().f;
          y=q.front().s;
          q.pop();
          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]--;
          }
     }
}
void update2(int a, int b) {
     while(!q.empty())
     q.pop();
     q.push({a,b});
     while (!q.empty()) {
          x=q.front().f;
          y=q.front().s;
          q.pop();
          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]--;
          }
     }
}
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;
              // cout<<r[i][j]<<" ";
          }
     //     cout<<endl;
     }
      cin>>qq;
     for (int i=1; i<=qq; i++) {
          cin>>x>>y;
          if (r[x][y]==1) {
               cout<<1<<endl;
               continue;
          }
          if (mp[x+y]==1) {
               cout<<0<<endl;
               continue;
          }
          cout<<1<<endl;
          mp[x+y]--;
          r[x][y]=1;
          update1(x,y);
          update2(x,y);
     }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95