Submission #1311472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311472		samarthkulkarni	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	19 / 100	100 ms	32352 KiB

mushrooms

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

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


ll r, c, d, k;

struct SegTree {
	vi lzy, tree;
	ll n;
	SegTree (ll _n) {
		n = _n;
		lzy.resize(4*n);
		tree.resize(4*n);
	}

	void push(int id, int l, int r) {
		if (!lzy[id]) return;

		tree[id] += lzy[id];

		if (l != r) {
			lzy[2*id] += lzy[id];
			lzy[2*id+1] += lzy[id];
		}

		lzy[id] = 0;
	}

	void update(int id, int l, int r, int L, int R) {
		push(id, l, r);
		if (L > r || l > R) return;
		if (L <= l && R >= r) {
			lzy[id]++;
			push(id, l, r);
			return;
		}
		int mid = (l + r)/2;
		update(2*id, l, mid, L, R);
		update(2*id+1, mid+1, r, L, R);
		tree[id] = tree[2*id] + tree[2*id+1];
	}

	ll query(int id, int l, int r, int pos) {
		push(id, l, r);
		if (pos < l || pos > r) return 0;
		if (l  == r) return tree[id];
		int mid = (l + r)/2;

		return query(2*id, l, mid, pos) + query(2*id+1, mid+1, r, pos);
	}


	void update(int l, int r) {
		l = max(0, l);
		r = min(r, int(c-1));
		update(1, 0, n-1, l, r);
	}

	ll query(int pos) {return query(1, 0, n-1, pos);}
};


void solution() {
	
	cin >> r >> c >> d >> k;

	string a; cin >> a;

	SegTree m(c);

	for (int i = 0; i < c; i++) {
		if (a[i] == 'S') m.update(i-d, i+d);
	}

	ll ans = 0;
	for (int i = 0; i < c; i++) {
		if (a[i] == 'M') ans += (m.query(i) >= k);
	}

	cout << ans << endl;
}

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