Submission #75157687

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <inttypes.h>
#define MAX 512345
#define BIT_MAX (MAX * 2)
int bit_table[BIT_MAX];
void bit_add(int pos, int value) {
  pos++;
  while (pos <= BIT_MAX) {
    bit_table[pos - 1] += value;
    pos += pos & (-pos);
  }
}
int bit_sum(int pos) {
  int sum = 0;
  pos++;
  while (pos > 0) {
    sum += bit_table[pos - 1];
    pos -= pos & (-pos);
  }
  return sum;
}
int N;
char S[MAX];
int cnt_list[MAX];
int main(void) {
  int i, cnt = 0, pos = MAX - 1;
  int64_t ans = 0;
  if (fgets(S, sizeof(S), stdin) == NULL || sscanf(S, "%d", &N) != 1) return 1;
  if (fgets(S, sizeof(S), stdin) == NULL) return 1;
  for (i = 0; i < N; i++) {
    cnt += (S[i] == 'B') - (S[i] == 'A');
    cnt_list[i] = cnt;
    bit_add(cnt + MAX, 1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define MAX 512345

#define BIT_MAX (MAX * 2)

int bit_table[BIT_MAX];

void bit_add(int pos, int value) {
	pos++;
	while (pos <= BIT_MAX) {
		bit_table[pos - 1] += value;
		pos += pos & (-pos);
	}
}

int bit_sum(int pos) {
	int sum = 0;
	pos++;
	while (pos > 0) {
		sum += bit_table[pos - 1];
		pos -= pos & (-pos);
	}
	return sum;
}

int N;
char S[MAX];

int cnt_list[MAX];

int main(void) {
	int i, cnt = 0, pos = MAX - 1;
	int64_t ans = 0;
	if (fgets(S, sizeof(S), stdin) == NULL || sscanf(S, "%d", &N) != 1) return 1;
	if (fgets(S, sizeof(S), stdin) == NULL) return 1;
	for (i = 0; i < N; i++) {
		cnt += (S[i] == 'B') - (S[i] == 'A');
		cnt_list[i] = cnt;
		bit_add(cnt + MAX, 1);
	}
	for (i = 0; i < N; i++) {
		ans += bit_sum(pos);
		bit_add(cnt_list[i] + MAX, -1);
		pos += (S[i] == 'B') - (S[i] == 'A');
	}
	printf("%" PRId64 "\n", ans);
	return 0;
}

/*

B の数から A の数を引いて、負になればおｋ
最初から最後までカウント → BIT で累積和
最初から削っていく → 解釈をシフト

*/

Submission Info

Judge Result