Submission #70602698


Source Code Expand

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
	while (abs(ok - ng) > 1) {
		T mid = (ok + ng) / 2;
		(f(mid) ? ok : ng) = mid;
	}
	return ok;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, a, b; cin >> n >> a >> b;
	string s; cin >> s;
	vector<int>ca(n + 1), cb(n + 1);
	rep(i, n) {
		ca[i + 1] = ca[i];
		cb[i + 1] = cb[i];
		if (s[i] == 'a')ca[i + 1]++;
		else cb[i + 1]++;
	}
	long long ans = 0;
	rep(i, n) {
		auto f = [&](const long long x)->bool {
			int cnt = ca[x] - ca[i];
			return cnt >= a;
		};
		auto g = [&](const long long x)->bool {
			int cnt = cb[x] - cb[i];
			return cnt < b;
		};
		if (!f(n))continue;
		auto ia = binarySearch<int>(n, i, f) - 1;//l
		auto ib = binarySearch<int>(i, n + 1, g);//r
		//cout << i << " " << ia << " " << ib << endl;
	//	if (ib < ia)continue;
		ans += max(0, ib - ia);
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task C - Truck Driver
User kwm_t
Language C++23 (GCC 15.2.0)
Score 300
Code Size 1794 Byte
Status AC
Exec Time 36 ms
Memory 6164 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 2
AC × 25
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All hand.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
hand.txt AC 1 ms 3572 KiB
random_01.txt AC 25 ms 6108 KiB
random_02.txt AC 22 ms 6148 KiB
random_03.txt AC 24 ms 6148 KiB
random_04.txt AC 24 ms 6096 KiB
random_05.txt AC 35 ms 6088 KiB
random_06.txt AC 35 ms 6148 KiB
random_07.txt AC 35 ms 5968 KiB
random_08.txt AC 35 ms 6148 KiB
random_09.txt AC 23 ms 6080 KiB
random_10.txt AC 26 ms 6116 KiB
random_11.txt AC 27 ms 5964 KiB
random_12.txt AC 22 ms 6096 KiB
random_13.txt AC 35 ms 6012 KiB
random_14.txt AC 36 ms 6148 KiB
random_15.txt AC 35 ms 6084 KiB
random_16.txt AC 35 ms 6080 KiB
random_17.txt AC 35 ms 6164 KiB
random_18.txt AC 35 ms 6092 KiB
random_19.txt AC 4 ms 6028 KiB
random_20.txt AC 3 ms 6144 KiB
random_21.txt AC 34 ms 6064 KiB
random_22.txt AC 4 ms 6112 KiB
sample_01.txt AC 1 ms 3580 KiB
sample_02.txt AC 1 ms 3580 KiB