제출 #1328219

#제출 시각아이디문제언어결과실행 시간메모리
1328219ninstroyerCollecting Mushrooms (NOI18_collectmushrooms)C++20
60 / 100
2092 ms14440 KiB
#include<bits/stdc++.h>
using namespace std;

int n,m,d,k;
vector<pair<int,int>> sprink, mush;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>d>>k;
    vector<vector<char>> mat(n+1,vector<char>(m+1));
    vector<vector<int>> cnt(n+1,vector<int>(m+1,0));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin>>mat[i][j];
            if(mat[i][j] == 'M') mush.push_back({j,i});
            if(mat[i][j] == 'S') sprink.push_back({j+d,i});
        }
    }
    sort(mush.begin(),mush.end());
    sort(sprink.begin(),sprink.end());
    int add = 0;
    int rem = 0;
    set<pair<int,int>> s;
    for(auto [x,y] : sprink)
    {
        while(add < mush.size() && mush[add].first <= x) s.insert({mush[add].second,mush[add].first}),add++;
        while(rem < mush.size() && mush[rem].first < x-2*d) s.erase({mush[rem].second,mush[rem].first}),rem++;
        for(auto itr = s.lower_bound({y-d,-1e9}); itr != s.end() && itr->first <= y+d; itr++) cnt[itr->first][itr->second]++;
    }
    int res = 0;
    for(int i = 0 ; i < mush.size(); i++)
    {
        auto [x,y] = mush[i];
        if(cnt[y][x] >= k) res++;
    }
    cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...