結果

問題 No.1490 スライムと爆弾
コンテスト
ユーザー sgsw
提出日時 2021-04-30 03:06:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 396 ms / 2,000 ms
コード長 3,558 bytes
コンパイル時間 3,185 ms
コンパイル使用メモリ 202,616 KB
最終ジャッジ日時 2025-01-21 02:19:37
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ALL(a) a.begin(),a.end()
#define rep(i,n) for (int i = 0; i < n; i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i, n) for (int i = (n); i > 0; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
template<class T> ostream& operator << (ostream &s, vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template <class T>bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template <class T>bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}
using P  = pair<int,int>;
const int inf = 1e18;
template <class T>int count_smaller_than(vector<T> & V,T x){
    auto itr = lower_bound(V.begin(),V.end(),x);
    return itr - V.begin();
}
template <class T>int smaller_than(vector<T> & V,T x){
    auto itr = lower_bound(V.begin(),V.end(),x);
    if (itr == V.begin()){return -inf;}
    return V[itr - V.begin() - 1];
}
template<class T> vector<T> push(vector<T> & V){
    vector<pair<T,int>> A;
    vector<T> res(V.size());
    for (int i = 0; i < V.size(); i++){
        A.push_back(P{V[i],i});
    }
    sort(A.begin(),A.end());
    T saved_val;
    int prev_idx = 1;
    for (int i = 0; i < V.size(); i++){
        auto [val,idx] = A[i];
        if (i == 0){res[idx] = 1;saved_val = val;prev_idx = 1;continue;}
        if (saved_val == val){res[idx] =prev_idx;continue;}
        else{saved_val = val;prev_idx++;res[idx] = prev_idx;continue;}
    }
    return res;
}

template <class T = int>T gcd(T a, T b){return (b == 0) ? a : gcd(b, a % b);}
template <class T = int>T lcm(T a, T b){return a / gcd(a, b) * b;}
template<class T = int>T powMod(T x, T k, T m) {if (k == 0){return (T)1;}if (k % 2 == 0) {return powMod(x*x % m, k/2, m);}else{return x*powMod(x, k-1, m) % m;}}
template <class T = int>T extgcd(T a,T b,T &x,T &y){T g = a;x = 1;y = 0;if (b != 0) {g = extgcd(b, a % b, y, x), y -= (a / b) * x;}return g;}
template<class T = int> T invMod(T a,T m){T x,y;if (extgcd(a, m, x, y) == 1) {return (x + m) % m;}else{return -1;}}

const int MAXN = 2010;

vector<vector<int>> C(MAXN,vector<int>(MAXN,0));


int field_damamge_sum(int rl,int rr,int cl,int cr){
    return C[rr][cr] + C[rl - 1][cl - 1] - C[rl - 1][cr] - C[rr][cl - 1];
}

void bomb_update(int rl,int rr,int cl,int cr,int d){
    C[rl][cl] += d;
    C[rl][cr + 1] -= d;
    C[rr + 1][cl] -= d;
    C[rr + 1][cr + 1] += d;
    return;
}

using slime = tuple<int,int,int,int,int>;

signed main(){
    int h,w,n,m;
    cin>>h>>w>>n>>m;
    vector<slime> Slimes;
    rep(i,n){
        int a,b,c,d,e;
        cin>>a>>b>>c>>d>>e;
        auto s = slime{a,b,c,d,e};
        Slimes.push_back(s);
    }
    rep(i,m){
        int x,y,b,c;
        cin>>x>>y>>b>>c;
        int rl = max(1ll,x - b);
        int rr = min(h,x + b);
        int cl = max(1ll,y - b);
        int cr = min(w,y + b);
        bomb_update(rl,rr,cl,cr,c);
    }
    rep1(i,h)rep1(j,w){
        int x = C[i][j];
        C[i][j + 1] += x;
    }
    rep1(i,h)rep1(j,w){
        int x = C[i][j];
        C[i + 1][j] += x;
    }
  
    rep1(i,h)rep1(j,w){
        int x = C[i][j];
        C[i][j + 1] += x;
    }
    rep1(i,h)rep1(j,w){
        int x = C[i][j];
        C[i + 1][j] += x;
    }
    int ans = 0;
    for (auto s : Slimes){
        auto [rl,rr,cl,cr,h] = s;
        //cout << field_damamge_sum(rl,rr,cl,cr) << endl;
        if (field_damamge_sum(rl,rr,cl,cr) < h)ans++;
    }
    cout << ans << endl;
    return 0;
}
0