結果

問題 No.60 魔法少女
コンテスト
ユーザー yaoshimax
提出日時 2015-02-22 20:26:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 830 ms / 5,000 ms
コード長 3,304 bytes
コンパイル時間 929 ms
コンパイル使用メモリ 96,896 KB
実行使用メモリ 35,072 KB
最終ジャッジ日時 2024-06-23 21:52:57
合計ジャッジ時間 10,046 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:107:9: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  107 |    scanf("%d%d",&N,&K);
      |    ~~~~~^~~~~~~~~~~~~~
main.cpp:111:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  111 |       scanf("%d%d%d",&X,&Y,&H);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:118:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  118 |       scanf("%d%d%d%d%d",&X,&Y,&W,&H,&D);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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