제출 #734206

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734206		vjudge1	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	70 ms	36532 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

template<typename... T>
void see(T&... args) {((cin >> args), ...);}
template<typename... T>
void put(T&&... args) {((cout << args << ' '), ...);}
template<typename... T>
void putl(T&&... args) {((cout << args << ' '), ...); cout << '\n';}

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define F first
#define S second
#define ii pair<int, int>

#define vt vector
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz size()

#define endl '\n'

#define rep(i,a,b) for(int i=a; i<=b; i++)
#define rev(i,b,a) for(int i=b; i>=a; i--)

#define reada(a,x,y) for(int i=x; i<=y; i++){cin >> a[i];}

const int Mxn = 1e6, Nxn = 2*1e5, Mxm = 5e5+5, Nxm = 1005, Dxn = 1e9+1;

int r, c, d, k;
vt<ii> m;
vt<vt<int>> bit;

void update(int x, int y, int val) {
    for(; x <= c; x += (x & -x)) {
        for(int i = y; i <= r; i += (i & -i))
            bit[x][i] += val;
    }
}

int query(int x1, int y1, int x2, int y2){
    int ans = 0;
    for(int i = x2; i; i -= (i & -i)) 
        for(int j = y2; j; j -= (j & -j))
            ans += bit[i][j];
    for(int i = x2; i; i -= (i & -i))
        for(int j = y1 - 1; j; j -= (j & -j))
            ans -= bit[i][j];
    for(int i = x1-1; i; i -= (i & -i))
        for(int j = y2; j; j-= (j & -j))
            ans -= bit[i][j];
    for(int i = x1-1; i; i -= (i & -i))
        for(int j = y1-1; j; j-= (j & -j))
            ans += bit[i][j];

    return ans;
}

void solve() {
    see(r, c, d, k);
    bit.resize(c+1, vt<int>(r+1, 0));
    rep(i,1,r) {
        rep(j,1,c) {
            char x; see(x);
            if(x == 'M') m.pb({i, j});
            if(x == 'S') update(j, i, 1);
        }
    }
    int s = 0, ans = 0;
    rep(i,0,m.size()-1) {
        s = 0;
        int x1 = m[i].F - d, y1 = m[i].S - d;
        int x2 = m[i].F + d, y2 = m[i].S + d;

        if(x1 < 1) x1 = 1;
        if(y1 < 1) y1 = 1;
        if(x2 > r) x2 = r;
        if(y2 > c) y2 = c;
        s += query(y1, x1, y2, x2);
        if(s >= k) ans++;
    }
    cout << ans;
    return;
}

signed main() { IOS
    int t=1;
    //cin >> t;
    while(t--) {
        solve();
        cout << endl;
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mushrooms.cpp: In function 'void solve()':
mushrooms.cpp:30:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | #define rep(i,a,b) for(int i=a; i<=b; i++)
......
   77 |     rep(i,0,m.size()-1) {
      |         ~~~~~~~~~~~~~~            
mushrooms.cpp:77:5: note: in expansion of macro 'rep'
   77 |     rep(i,0,m.size()-1) {
      |     ^~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21