yukicoder No.60 魔法少女

問題

問題概要

省略

解法

2次元imos法を使えば楽なんですね。
imos法

いもす法 - いもす研 (imos laboratory)

BITとかsegtree使うのかな、て感じだった。
2次元BIT

http://hos.ac/slides/20140319_bit.pdf

ミス

imos!!

コード

2次元imos法

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n, k;
int x[100010], y[100010], hp[100010];
int imos[1510][1510];

//imos
int main(void){
    cin >> n >> k;
    rep(i, n){
        cin >> x[i] >> y[i] >> hp[i];
        x[i] += 500; y[i] += 500;
    }

    rep(i, 1510)rep(j, 1510) imos[i][j] = 0;

    rep(i, k){
        int ax, ay, w, h, d;
        cin >> ax >> ay >> w >> h >> d;
        ax += 500; ay += 500;
        imos[ay][ax] += d;//左上
        imos[ay][ax + w + 1] -= d;//右上
        imos[ay + h + 1][ax] -= d;//左下
        imos[ay + h + 1][ax + w + 1] += d;//右下
    }

    //横方向への累積和
    rep(i, 1505)rep(j, 1505){
        imos[i][j + 1] += imos[i][j];
    }
    //縦方向の累積和
    rep(i, 1505)rep(j, 1505){
        imos[i + 1][j] += imos[i][j];
    }

    ll ans = 0;
    rep(i, n){
        int ty = y[i], tx = x[i];
        ans += max((ll)0, (ll)(hp[i] - imos[ty][tx]));
    }
    printf("%lld\n", ans);
    return 0;
}

2次元BIT

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

//2次元BIT
const int MAX_W = 1010, MAX_H = 1010;
int bit[MAX_W + 1][MAX_H + 1];
void add(int a, int b, ll w){
    for (int y = a; y < MAX_W; y += y & -y){
        for (int x = b; x < MAX_H; x += x & -x){
            bit[y][x] += w;
        }
    }
}

ll sum(int a, int b){
    ll ret = 0;
    for (int y = a; y > 0; y -= y & -y){
        for (int x = b; x > 0; x -= x & -x){
            ret += bit[y][x];
        }
    }
    return ret;
}

int n, k;
int x[100010], y[100010], hp[100010];

int main(void){
    cin >> n >> k;
    rep(i, n){
        cin >> x[i] >> y[i] >> hp[i];
        x[i] += 501; y[i] += 501;// -500を1に1index
    }
    rep(i, k){
        int ax, ay, w, h, d;
        cin >> ax >> ay >> w >> h >> d;
        ax += 501; ay += 501;
        add(ay, ax, d);
        add(ay + h + 1, ax, -d);
        add(ay, ax + w + 1, -d);
        add(ay + h + 1, ax + w + 1, d);
    }

    ll ans = 0;
    rep(i, n){
        ans += max((ll)0, hp[i] - sum(y[i], x[i]));
    }
    printf("%lld\n", ans);
    return 0;
}