結果

問題 No.325 マンハッタン距離2
ユーザー beetbeet
提出日時 2018-12-05 17:33:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,727 bytes
コンパイル時間 1,947 ms
コンパイル使用メモリ 199,152 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-26 13:23:56
合計ジャッジ時間 3,227 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int ans=0;
  auto solve=
    [&](Int x1,Int y1,Int x2,Int y2,Int d){
      Int xx1=x1,xx2=x2;
      Int yy1=y1,yy2=y2;
      
      chmax(xx1,0);
      chmax(yy1,0);
      if(xx2<0||yy2<0) return;
      if(xx1+yy1>d) return;
      //cout<<xx1<<" "<<yy1<<":"<<xx2<<" "<<yy2<<endl;
      
      if(xx2+yy2<=d){
        ans+=(xx2-xx1+1)*(yy2-yy1+1);
        return;
      }

      Int x=d-yy1,y=d-xx1;
      Int a=d-yy2,b=d-xx2;
      
      if(x<=xx2&&y<=yy2){
        assert(x-xx1==y-yy1);
        ans+=(x-xx1+1 + 1)*(x-xx1+1)/2;
        return;
      }
      
      if(x<=xx2&&y>yy2){
        ans+=(x-xx1+1 + a-xx1+1)*(yy2-yy1+1)/2;
        return;
      }
      
      if(x>xx2&&y<=yy2){
        ans+=(y-yy1+1 + b-yy1+1)*(xx2-xx1+1)/2;
        return;
      }
      
      assert(xx2-a==yy2-b);
      ans+=(xx2-xx1+1)*(yy2-yy1+1);
      ans-=(xx2-a+1)*(xx2-a)/2;
    };
  
  Int x1,y1,x2,y2,d;
  cin>>x1>>y1>>x2>>y2>>d;

  solve( x1, y1, x2, y2,d);
  //cout<<ans<<endl;
  solve( x1,-y2, x2,-y1,d);
  //cout<<ans<<endl;
  solve(-x2, y1,-x1, y2,d);
  //cout<<ans<<endl;
  solve(-x2,-y2,-x1,-y1,d);
  //cout<<ans<<endl;
  
  if(x1<=0&&0<=x2){
    Int yy1=y1,yy2=y2;
    chmax(yy1,-d);
    chmin(yy2,d);
    ans-=max(yy2-yy1+1,0LL);
  }
  //cout<<ans<<endl;
  if(y1<=0&&0<=y2){
    Int xx1=x1,xx2=x2;
    chmax(xx1,-d);
    chmin(xx2,d);
    ans-=max(xx2-xx1+1,0LL);
  }
  //cout<<ans<<endl;
  
  if(x1<=0&&0<=x2&&y1<=0&&0<=y2) ans--;
  cout<<ans<<endl;
  return 0;
}
0