結果

問題 No.60 魔法少女
コンテスト
ユーザー not_522
提出日時 2015-08-19 14:11:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 185 ms / 5,000 ms
コード長 2,460 bytes
コンパイル時間 1,318 ms
コンパイル使用メモリ 167,032 KB
実行使用メモリ 15,880 KB
最終ジャッジ日時 2024-07-18 10:30:00
合計ジャッジ時間 3,936 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

template<class Value, bool rangeAdd = false> class CumulativeSum2D {
private:
  struct RangeValue {
    int i, j, y, x;
    Value v;
    RangeValue(int i, int j, int y, int x, Value v) : i(i), j(j), y(y), x(x), v(v) {}
  };

  vector<vector<Value>> val;
  vector<RangeValue> rangeValue;

public:
  CumulativeSum2D(int n, int m) : val(n + 1, vector<Value>(m + 1, Value(0))) {}
  
  template<typename T> CumulativeSum2D(T v) {
    int n = v.size();
    int m = v.front().size();
    for (int i = 0; i < n + 1; ++i) val.emplace_back(m + 1, Value(0));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        val[i + 1][j + 1] = val[i][j + 1] + val[i + 1][j] - val[i][j] + v[i][j];
      }
    }
  }

  void add(int i, int j, Value v) {
    add(i, j, i + 1, j + 1, v);
  }

  void add(int i, int j, int y, int x, Value v) {
    rangeValue.emplace_back(i, j, y, x, v);
  }

  // [(i,j), (y,x))
  Value sum(int i, int j, int y, int x) {
    if (rangeAdd && !rangeValue.empty()) {
      int n = val.size() - 1;
      int m = val.front().size() - 1;
      for (int k = 0; k < 2; ++k) {
        for (int i = 0; i < n; ++i) {
          for (int j = 0; j < m; ++j) {
            val[i + 1][j + 1] = val[i + 1][j + 1] - val[i][j + 1] - val[i + 1][j] + val[i][j];
          }
        }
      }
      for (const auto& v : rangeValue) {
        val[v.i + 1][v.j + 1] += v.v;
        if (v.y < n) val[v.y + 1][v.j + 1] -= v.v;
        if (v.x < m) val[v.i + 1][v.x + 1] -= v.v;
        if (v.y < n && v.x < m) val[v.y + 1][v.x + 1] += v.v;
      }
      for (int k = 0; k < 2; ++k) {
        for (int i = 0; i < n; ++i) {
          for (int j = 0; j < m; ++j) {
            val[i + 1][j + 1] += val[i][j + 1] + val[i + 1][j] - val[i][j];
          }
        }
      }
      rangeValue.clear();
    }
    return val[y][x] - val[i][x] - val[y][j] + val[i][j];
  }

  Value value(int i, int j) {
    return sum(i, j, i + 1, j + 1);
  }
};

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> x(n), y(n), hp(n);
  for (int i = 0; i < n; ++i) cin >> x[i] >> y[i] >> hp[i];
  CumulativeSum2D<int, true> sum(1501, 1501);
  for (int i = 0; i < k; ++i) {
    int ax, ay, w, h, d;
    cin >> ax >> ay >> w >> h >> d;
    sum.add(ay + 500, ax + 500, ay + h + 501, ax + w + 501, d);
  }
  int res = 0;
  for (int i = 0; i < n; ++i) res += max(0, hp[i] - sum.value(y[i] + 500, x[i] + 500));
  cout << res << endl;
}
0