No.60 魔法少女 - yukicoder
- いもす法。はじめ Segmetn Tree を2つ用意して...とかと思ったが違った。
- いもす法のことは知ってたけど、使うのは初めてだったんで勉強になった
- 右上を +1 拡張しわすれそうになった。
class MagicGirl {
public:
void solve(void) {
int N,K;
cin>>N>>K;
int offset = 2;
int W,H,ox,oy;
W = H = 1000 + offset;
ox = W/2;
oy = H/2;
vector<tuple<int,int,int>> monster;
REP(i, N)
{
int x,y,hp;
cin>>x>>y>>hp;
x += ox;
y += oy;
monster.emplace_back(x,y,hp);
}
vector<vector<int>> damage(H+1, vector<int>(W+1, 0));
REP(i,K)
{
int x,y,w,h,d;
cin>>x>>y>>w>>h>>d;
x += ox;
y += oy;
damage[min(y+h+1,H)][min(x+w+1,W)] += d;
damage[min(y+h+1,H)][x] -= d;
damage[y][min(x+w+1,W)] -= d;
damage[y][x] += d;
}
vector<vector<int>> sum(H+1, vector<int>(W+1, 0));
FOR(y,1,H+1)
FOR(x,1,W+1)
sum[y][x] += sum[y][x-1] + sum[y-1][x] - sum[y-1][x-1] + damage[y][x];
int ans = 0;
for (auto m : monster)
{
int x,y,hp;
tie(x,y,hp) = m;
ans += max(0,hp - sum[y][x]);
}
cout<<ans<<endl;
}
};