Submission #70710107

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <inttypes.h>
int N, A, B;
char S[312345];
int acnt[312345], bcnt[312345];
int get_first_ge(const int* arr, int target) {
  int l = 0, ge = N + 1;
  while (l + 1 < ge) {
    int m = l + (ge - l) / 2;
    if (arr[m] >= target) ge = m; else l = m;
  }
  return ge;
}
int main(void) {
  int i;
  uint64_t ans = 0;
  if (scanf("%d%d%d", &N, &A, &B) != 3) return 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

int N, A, B;
char S[312345];

int acnt[312345], bcnt[312345];

int get_first_ge(const int* arr, int target) {
	int l = 0, ge = N + 1;
	while (l + 1 < ge) {
		int m = l + (ge - l) / 2;
		if (arr[m] >= target) ge = m; else l = m;
	}
	return ge;
}

int main(void) {
	int i;
	uint64_t ans = 0;
	if (scanf("%d%d%d", &N, &A, &B) != 3) return 1;
	if (scanf("%312343s", S + 1) != 1) return 1;
	for (i = 1; i <= N; i++) {
		acnt[i] = acnt[i - 1] + (S[i] == 'a');
		bcnt[i] = bcnt[i - 1] + (S[i] == 'b');
	}
	for (i = 0; i < N; i++) {
		int a_ge = get_first_ge(acnt, A + acnt[i]);
		int b_ge = get_first_ge(bcnt, B + bcnt[i]);
		if (a_ge < b_ge) ans += b_ge - a_ge;
	}
	printf("%" PRIu64 "\n", ans);
	return 0;
}

Submission Info

Judge Result