1080C - Masha and two friends ～白黒タイルを塗る。領域の重なり～

• Quiz
  • https://codeforces.com/problemset/problem/1080/C
• AC
  • https://codeforces.com/contest/1080/submission/100064787
• 感想
  • 解法はeditorialの通り。https://codeforces.com/blog/entry/63436
  • 二次元累積和に似た考え方をすることで指定領域内のblack, whiteを数えることができる
  • 領域の重なりはmax, minでシンプルに表現でき、重ならない場合の判定も楽
  • 時間がかかったけれど学びも多かった

// (x,y)
ll w(ll a, ll b){
  if(a<=0 or b<=0) return 0;
  // 以降、a>0 && b>0
  return ceil_div(a,2) * ceil_div(b,2) + (a/2) * (b/2);
}

struct area{
  ll x0,y0; // 左下
  ll x1,y1; // 右上

  // 左下と右上の位置関係がおかしい場合はfalse
  bool is_valid(){
    if(x1<x0 or y1<y0)return false;
    return true;
  }

  string ToString(){
    stringstream ss;
    ss << x0 << ' ' << y0 << ' ' << x1 << ' ' << y1;
    return ss.str();
  }
};

// 領域内 white (a,b) to (c,d)
ll WH(area r){
  ll a = r.x0;
  ll b = r.y0;
  ll c = r.x1;
  ll d = r.y1;
  return w(c,d) - w(a-1,d) - w(c,b-1) + w(a-1,b-1);
}

// 領域内 black
ll BL(area r){
  ll w = r.x1 - r.x0 + 1;
  ll h = r.y1 - r.y0 + 1;
  return w*h - WH(r);
}

// 重なる領域
area cross_area(area a, area b){
  // 左下はmaxを取るのです
  ll x = max(a.x0, b.x0);
  ll y = max(a.y0, b.y0);
  // 右上はminを取るのです
  ll x2 = min(a.x1, b.x1);
  ll y2 = min(a.y1, b.y1);
  return {x,y,x2,y2};
}

void test(){
  area a0 = {2,2,4,4};
  area a1 = {4,0,7,6};
  debug(cross_area(a0,a1).ToString());
}

area get_area(){
  ll x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  return {x1,y1,x2,y2};
}

// for codeforces
void solve(){
  ll H,W;cin>>H>>W;

  area area0 = get_area();
  area area1 = get_area();
  area area2 = cross_area(area0, area1);

  ll white = w(W,H);
  ll black = W*H-white;

  // whiteに塗ります
  // その領域のblackの数だけ変化するが、重なる領域に注意する
  {
    ll b = BL(area0);
    if(area2.is_valid()){
      b -= BL(area2); // 重なる領域分の黒を数えない
    }
    white += b;
    black -= b;
  }

  // blackに塗ります
  {
    ll w = WH(area1);
    white -= w;
    black += w;
  }

  p2(white,black);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    // input
    ll N;cin>>N;    
    while(N--)solve();
    return 0;
}