結果

問題 No.1490 スライムと爆弾
ユーザー sgswsgsw
提出日時 2021-04-30 03:06:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 275 ms / 2,000 ms
コード長 3,558 bytes
コンパイル時間 2,122 ms
コンパイル使用メモリ 210,868 KB
実行使用メモリ 41,604 KB
最終ジャッジ日時 2023-09-25 03:12:44
合計ジャッジ時間 8,338 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 26 ms
34,576 KB
testcase_01 AC 25 ms
34,476 KB
testcase_02 AC 26 ms
34,740 KB
testcase_03 AC 26 ms
34,604 KB
testcase_04 AC 25 ms
34,956 KB
testcase_05 AC 25 ms
34,644 KB
testcase_06 AC 26 ms
34,480 KB
testcase_07 AC 25 ms
35,104 KB
testcase_08 AC 26 ms
34,480 KB
testcase_09 AC 26 ms
34,476 KB
testcase_10 AC 26 ms
34,976 KB
testcase_11 AC 25 ms
34,472 KB
testcase_12 AC 25 ms
34,516 KB
testcase_13 AC 134 ms
37,412 KB
testcase_14 AC 160 ms
41,604 KB
testcase_15 AC 90 ms
35,976 KB
testcase_16 AC 126 ms
37,356 KB
testcase_17 AC 74 ms
36,136 KB
testcase_18 AC 159 ms
40,368 KB
testcase_19 AC 142 ms
40,560 KB
testcase_20 AC 109 ms
37,684 KB
testcase_21 AC 71 ms
36,024 KB
testcase_22 AC 148 ms
40,032 KB
testcase_23 AC 25 ms
34,472 KB
testcase_24 AC 26 ms
34,472 KB
testcase_25 AC 180 ms
40,980 KB
testcase_26 AC 178 ms
40,936 KB
testcase_27 AC 179 ms
40,160 KB
testcase_28 AC 129 ms
34,476 KB
testcase_29 AC 132 ms
34,744 KB
testcase_30 AC 275 ms
40,668 KB
権限があれば一括ダウンロードができます

ソースコード

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