oj.uz

Submission #891104

# Submission time Handle Problem Language Result Execution time Memory
891104 2023-12-22T07:48:07 Z thunopro Collecting Mushrooms (NOI18_collectmushrooms) C++14
100 / 100
 43 ms 36108 KB 
#include<bits/stdc++.h>
using namespace std ;
#define maxn 500009 
#define ll long long
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef vector<ll> vl ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 
typedef pair<ll,ll> pll ;  

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;} 
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow(a,n/2) ;
	if ( n % 2 ) return (1ll*res*res%mod*a%mod) ; 
	else return 1ll*res*res%mod ; 
}

int n , m , k , d ; 
vector <char> a [maxn] ; 

const int N = 1e4 + 9 ; 

int bit [N] ; 
vii event [maxn] ; 

void update ( int x , int y ) 
{
	while ( x < N ) bit [x] += y , x += (x&-x) ; 
}
int get ( int x ) 
{
	int res = 0 ; 
	while ( x ) res += bit [x] , x -= (x&-x) ; 
	return res ; 
}

void update ( int l , int r , int w ) 
{
	update (l,w) ; 
	update (r+1,-w) ; 
}

void solve () 
{
	for ( int j = 1 ; j <= m ; j ++ ) 
	{
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			if ( a [i][j] == 'S' ) 
			{
				int l = max (i-d,1) , r = min (i+d,n) ; 
				int col = max (j-d,1) ; 	
				event [col] . pb ({l,r}) ; 
				col = min (j+d+1,m+1) ; 
				event [col] . pb ({-l,-r}) ; 
			}
		}
	}
	
	int res = 0 ; 
	for ( int j = 1 ; j <= m ; j ++ ) 
	{
		sort (event[j].begin(),event[j].end()) ; 
		for ( auto x : event [j] ) 
		{
			int l = x.fi , r = x.se ; 
			if ( l < 0 ) update (abs(l),abs(r),-1) ; 
			else update (l,r,1) ; 
		}
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			if ( a [i][j] == 'M' && get (i) >= k ) res ++ ;  
		}
	}
	cout << res ; 
}

int main () 
{
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; cout.tie(0) ; 
//	rf () ; 	
	cin >> n >> m >> d >> k ; 
	if ( n < m ) 
	{
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			a [i] . resize (m+1) ; 
			for ( int j = 1 ; j <= m ; j ++ ) 
			{
				cin >> a [i][j] ; 
			}
		}
	}
	else 
	{
		for ( int j = 1 ; j <= m ; j ++ ) a [j] . resize (n+1) ; 
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			for ( int j = 1 ; j <= m ; j ++ ) 
			{
				cin >> a [j][i] ; 
			}
		}
		swap (n,m) ; 
	}
	
	solve () ; 
}

Compilation message

mushrooms.cpp: In function 'void rf()':
mushrooms.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 6 ms 23984 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 6 ms 23900 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 6 ms 23984 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 6 ms 23900 KB Output is correct
6 Correct 5 ms 23900 KB Output is correct
7 Correct 7 ms 23976 KB Output is correct
8 Correct 7 ms 24156 KB Output is correct
9 Correct 6 ms 23900 KB Output is correct
10 Correct 6 ms 23900 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23996 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 7 ms 23744 KB Output is correct
5 Correct 6 ms 23980 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24292 KB Output is correct
2 Correct 7 ms 24156 KB Output is correct
3 Correct 8 ms 24412 KB Output is correct
4 Correct 8 ms 24412 KB Output is correct
5 Correct 10 ms 24412 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28392 KB Output is correct
2 Correct 14 ms 25180 KB Output is correct
3 Correct 14 ms 25528 KB Output is correct
4 Correct 43 ms 36108 KB Output is correct
5 Correct 21 ms 28112 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 6 ms 23984 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 6 ms 23900 KB Output is correct
6 Correct 5 ms 23900 KB Output is correct
7 Correct 7 ms 23976 KB Output is correct
8 Correct 7 ms 24156 KB Output is correct
9 Correct 6 ms 23900 KB Output is correct
10 Correct 6 ms 23900 KB Output is correct
11 Correct 6 ms 23996 KB Output is correct
12 Correct 6 ms 23900 KB Output is correct
13 Correct 6 ms 23900 KB Output is correct
14 Correct 7 ms 23744 KB Output is correct
15 Correct 6 ms 23980 KB Output is correct
16 Correct 9 ms 24292 KB Output is correct
17 Correct 7 ms 24156 KB Output is correct
18 Correct 8 ms 24412 KB Output is correct
19 Correct 8 ms 24412 KB Output is correct
20 Correct 10 ms 24412 KB Output is correct
21 Correct 23 ms 28392 KB Output is correct
22 Correct 14 ms 25180 KB Output is correct
23 Correct 14 ms 25528 KB Output is correct
24 Correct 43 ms 36108 KB Output is correct
25 Correct 21 ms 28112 KB Output is correct
26 Correct 18 ms 26708 KB Output is correct
27 Correct 16 ms 25868 KB Output is correct
28 Correct 25 ms 28564 KB Output is correct
29 Correct 19 ms 26716 KB Output is correct
30 Correct 17 ms 26336 KB Output is correct