#include <iostream> #include <cstdlib> long long int tab_A[300001]; long long int tab_B[300001]; long long int tab_C[300001]; std::string chr; void load() { int i = 1; for (char c : chr) { if (c == 'a') tab_A[i] = tab_A[i - 1] + 1; else tab_A[i] = tab_A[i - 1]; if (c == 'b') tab_B[i] = tab_B[i - 1] + 1; else tab_B[i] = tab_B[i - 1]; if (c == 'c') tab_C[i] = tab_C[i - 1] + 1; else tab_C[i] = tab_C[i - 1]; i++; } } bool is_balanced(int a, int b) { int count_A = tab_A[b] - tab_A[a - 1], count_B = tab_B[b] - tab_B[a - 1], count_C = tab_C[b] - tab_C[a - 1]; if (count_A == 0) count_A = count_B > count_C ? count_B : count_C; if (count_B == 0) count_B = count_A > count_C ? count_A : count_C; if (count_C == 0) count_C = count_A > count_B ? count_A : count_B; return count_A == count_B && count_B == count_C && count_A == count_C; } int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cin >> chr; tab_A[0] = 0; tab_B[0] = 0; tab_C[0] = 0; load(); long long int full = 0; for (int i = 1; i <= chr.length(); i++) { for (int j = 1; j <= i; j++) { if (is_balanced(j, i)) full++; } } std::cout << full << std::endl; }
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <iostream> #include <cstdlib> long long int tab_A[300001]; long long int tab_B[300001]; long long int tab_C[300001]; std::string chr; void load() { int i = 1; for (char c : chr) { if (c == 'a') tab_A[i] = tab_A[i - 1] + 1; else tab_A[i] = tab_A[i - 1]; if (c == 'b') tab_B[i] = tab_B[i - 1] + 1; else tab_B[i] = tab_B[i - 1]; if (c == 'c') tab_C[i] = tab_C[i - 1] + 1; else tab_C[i] = tab_C[i - 1]; i++; } } bool is_balanced(int a, int b) { int count_A = tab_A[b] - tab_A[a - 1], count_B = tab_B[b] - tab_B[a - 1], count_C = tab_C[b] - tab_C[a - 1]; if (count_A == 0) count_A = count_B > count_C ? count_B : count_C; if (count_B == 0) count_B = count_A > count_C ? count_A : count_C; if (count_C == 0) count_C = count_A > count_B ? count_A : count_B; return count_A == count_B && count_B == count_C && count_A == count_C; } int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cin >> chr; tab_A[0] = 0; tab_B[0] = 0; tab_C[0] = 0; load(); long long int full = 0; for (int i = 1; i <= chr.length(); i++) { for (int j = 1; j <= i; j++) { if (is_balanced(j, i)) full++; } } std::cout << full << std::endl; } |