Submission #3440558

---

Source Code Expand

#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
int W,H,N;
int x1[1001],x2[1001],yy1[1001],yy2[1001];

int compress(int *z1,int *z2, int w){
  vector<int> zs(0);
  for(int i=0;i<N;i++){
    for(int d=0;d<=1;d++){
      int tz1 = z1[i]+d-1,tz2 = z2[i]+d;
      if(tz1 >= 0 && tz1 < w) zs.push_back(tz1);
      if(tz2 >= 0 && tz2 < w) zs.push_back(tz2);
    }
  }
  zs.push_back(0);
  zs.push_back(w-1);
  sort(zs.begin(),zs.end());
  zs.erase(unique(zs.begin(),zs.end()),zs.end());
  for(int i=0;i<N;i++){
    z1[i] = lower_bound(zs.begin(),zs.end(),z1[i])-zs.begin();
    z2[i] = lower_bound(zs.begin(),zs.end(),z2[i])-zs.begin();
  }
  return zs.size();
}
int main()
{
  int w,h,cnt=0;
  cin >> W >> H;
  cin >> N;
  REP(i,N){cin >> x1[i] >> yy1[i] >> x2[i] >> yy2[i];
    x2[i]--;yy2[i]--;
  }
  W = compress(x1,x2,W);
  H = compress(yy1,yy2,H);
  vector<vector<short> > imos = vector<vector<short> >(H+1,vector<short>(W+1,0));
  
  for(int i=0;i<N;i++){
    imos[yy1[i]][x1[i]] += 1;
    imos[yy2[i]+1][x1[i]] += -1;
    imos[yy1[i]][x2[i]+1] += -1;
    imos[yy2[i]+1][x2[i]+1] += 1;
  }
  
  
  //横いもす
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++){
      imos[i][j+1] += imos[i][j];
    }
  //縦いもす
  for(int j=0;j<W;j++)
    for(int i=0;i<H;i++){
      imos[i+1][j] += imos[i][j];
    }
  
  queue<P> que;
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++){
      if(imos[i][j] == 0){
      que.push(P(j,i));
      while(!que.empty()){
        P p=que.front();que.pop();
        if(p.first >= W || p.first < 0 || p.second >= H || p.second < 0)
          continue;
        if(imos[p.second][p.first] > 0)
          continue;
        imos[p.second][p.first] = 1;
        for(int k=0;k<4;k++)
          que.push(P(p.first+dx[k],p.second+dy[k]));
      }
      
      cnt++;
      }
    }
  cout << cnt << endl;
  return 0;
}

Submission Info

Judge Result