結果

問題 No.60 魔法少女
ユーザー yaoshimaxyaoshimax
提出日時 2015-02-22 20:26:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 823 ms / 5,000 ms
コード長 3,304 bytes
コンパイル時間 993 ms
コンパイル使用メモリ 102,972 KB
実行使用メモリ 34,844 KB
最終ジャッジ日時 2023-09-06 03:00:37
合計ジャッジ時間 10,245 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 358 ms
34,776 KB
testcase_01 AC 356 ms
34,644 KB
testcase_02 AC 360 ms
34,660 KB
testcase_03 AC 357 ms
34,716 KB
testcase_04 AC 588 ms
34,776 KB
testcase_05 AC 641 ms
34,720 KB
testcase_06 AC 808 ms
34,660 KB
testcase_07 AC 685 ms
34,648 KB
testcase_08 AC 578 ms
34,708 KB
testcase_09 AC 449 ms
34,776 KB
testcase_10 AC 780 ms
34,656 KB
testcase_11 AC 407 ms
34,844 KB
testcase_12 AC 561 ms
34,716 KB
testcase_13 AC 823 ms
34,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;


class BIT2D{
  /*binary indexed tree 2d*/
 private:
  vector< vector<long long> > data;
  int xsize;
  int ysize;
 public:
  BIT2D(int n, int m ): data(n+1,vector<long long>((m+1),0)),xsize(n),ysize(m){
    return;
  }
  long long getSum( int x1, int y1, int x2, int y2 ){
    // return getSum ((x1,y1), (x2,y2)] ... means [(x1+1,y1+1),(x,y)]
    return getSum_(x2,y2)-getSum_(x1,y2)-getSum_(x2,y1)+getSum_(x1,y1);
  }
  long long getSum_(int x, int y){
    // return getSum ((0,0), (x,y)] ... means [(1,1),(x,y)]
    long long ans = 0;
    for( int i = x ; 0 < i; i -=i&-i ){
      for( int j = y;  0 < j; j -= j&-j ){
        ans += data[i][j];
      }
    }
    return ans;
  }
  void add(int x, int y, int v){
    // add v to (x,y)
    for( int i = x ;  i <= xsize; i += i&-i ){
      for( int j = y ; j <= ysize; j+= j&-j ){
        data[i][j] += v;
      }
    }
    return;
  }
};



class BIT2DFILL{
   /*2 dimensional binary indexed tree, with filling 2d field */
   private:
      BIT2D bxy;
      BIT2D bx;
      BIT2D by;
      BIT2D bc;
   public:
      BIT2DFILL(int n,int m): bxy(n,m),bx(n,m),by(n,m),bc(n,m){
         return;
      }
      long long getSum_( int x, int y ){
         // return getSum of first l factors, ((0,0),(x,y)]
         //cout << bxy.getSum_(x,y) <<"*"<<x<<"*"<<y<<"+" <<bx.getSum_(x,y) <<"*"<<x<<"+" << by.getSum_(x,y) <<"*"<<y<< "+" << bc.getSum_(x,y)<<"=";
         return x*y*bxy.getSum_(x,y)+x*bx.getSum_(x,y)+y*by.getSum_(x,y)+bc.getSum_(x,y);;
      }
      long long getSum( int x1,int y1, int x2, int y2 ){
         // return getSum of ((x1,y1),(x2,y2)]
         return getSum_(x2,y2)-getSum_(x1,y2)-getSum_(x2,y1)+getSum_(x1,y1);
      }
      void add( int x1,int y1, int x2, int y2, int v){
         // add v in ((x1,y1),(x2,y2)]
         bxy.add(x1+1,y1+1,v);
         bxy.add(x1+1,y2+1,-v);
         bxy.add(x2+1,y1+1,-v);
         bxy.add(x2+1,y2+1,v);

         bx.add(x1+1,y1+1,-v*y1);
         bx.add(x1+1,y2+1,+v*y2);
         bx.add(x2+1,y1+1,+v*y1);
         bx.add(x2+1,y2+1,-v*y2);

         by.add(x1+1,y1+1,-v*x1);
         by.add(x1+1,y2+1,+v*x1);
         by.add(x2+1,y1+1,+v*x2);
         by.add(x2+1,y2+1,-v*x2);

         bc.add(x1+1,y1+1,v*x1*y1);
         bc.add(x1+1,y2+1,-v*x1*y2);
         bc.add(x2+1,y1+1,-v*x2*y1);
         bc.add(x2+1,y2+1,+v*x2*y2);
      }
};

int main(){
   int N,K;
   scanf("%d%d",&N,&K);
   BIT2DFILL b(1003,1003);
   for( int i = 0 ; i < N ; i++){
      int X,Y,H;
      scanf("%d%d%d",&X,&Y,&H);
      X+=501;
      Y+=501;
      b.add( X-1,Y-1,X,Y,H);
   }
   for( int i = 0 ; i < K ; i++ ){
      int X,Y,W,H,D;
      scanf("%d%d%d%d%d",&X,&Y,&W,&H,&D);
      X+=501;
      Y+=501;
      b.add(X-1,Y-1,X+W,Y+H,-D);
   }
   int ans=0;
   for( int i = 1; i <= 1002; i++ ){
      for( int j = 1; j <= 1002; j++ ){

         int p=b.getSum(i-1,j-1,i,j);
         if(p>0) ans+=p;
      }
   }
   printf("%d\n",ans);
   return 0;
}
0