#79505 (C++11) No.346 チワワ数え上げ問題

• 問題: No.346 チワワ数え上げ問題
• ユーザー: yudedako
• 提出日時: 2016-03-01 17:02:37
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 7 ms / 2,000 ms
• コード長: 1,342 bytes
• コンパイル時間: 597 ms
• コンパイル使用メモリ: 68,444 KB
• 実行使用メモリ: 4,576 KB
• 最終ジャッジ日時: 2023-10-24 19:20:23
• 合計ジャッジ時間: 1,508 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	1 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	1 ms; 4,348 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	2 ms; 4,348 KB
testcase_07	AC	1 ms; 4,348 KB
testcase_08	AC	1 ms; 4,348 KB
testcase_09	AC	1 ms; 4,348 KB
testcase_10	AC	5 ms; 4,348 KB
testcase_11	AC	3 ms; 4,348 KB
testcase_12	AC	4 ms; 4,348 KB
testcase_13	AC	4 ms; 4,348 KB
testcase_14	AC	2 ms; 4,348 KB
testcase_15	AC	4 ms; 4,348 KB
testcase_16	AC	4 ms; 4,348 KB
testcase_17	AC	5 ms; 4,348 KB
testcase_18	AC	4 ms; 4,348 KB
testcase_19	AC	4 ms; 4,348 KB
testcase_20	AC	6 ms; 4,576 KB
testcase_21	AC	7 ms; 4,348 KB
testcase_22	AC	6 ms; 4,348 KB
testcase_23	AC	2 ms; 4,348 KB
testcase_24	AC	1 ms; 4,348 KB
testcase_25	AC	2 ms; 4,348 KB

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <stack>
class Binaly_intersection_tree {
	using Val = unsigned long long int;
	using Idx = int;
public:
	Binaly_intersection_tree(const int &x) :vector(x) {};
	Val search(const Idx &i) const {
		return search_val(i);
	}
	void set_val(const Idx &i, const Val &val) {
		update(i, val);
	}
private:
	std::vector<Val> vector;
	Idx left_idx(const Idx &i) const {
		return i - ((i + 1) & (~i));
	}
	Idx up_idx(const Idx &i) const {
		return i + ((i + 1) & (~i));
	}
	void update(const Idx &i, const Val &val) {
		if (i < vector.size()) {
			vector.at(i) += val;
			update(up_idx(i), val);
		}
	}
	Val search_val(const Idx &i) const {
		if (i < 0) {
			return 0;
		}
		else {
			return vector.at(i) + search_val(left_idx(i));
		}
	}
};

int main() {
	std::string str;
	std::cin >> str;
	std::stack<int> stack;
	Binaly_intersection_tree bit(str.size());
	for (auto i = 0; i < str.size(); ++i) {
		switch (str.at(i)) {
		case 'c':
			stack.push(i);
			break;
		case 'w':
			bit.set_val(i, 1);
		}
	}
	const auto &maxw = bit.search(str.size() - 1);
	unsigned long long int res = 0;
	for (; stack.size() != 0;stack.pop()) {
		const auto &head = stack.top();
		const unsigned long long  w = maxw - bit.search(head);
		res += w * (w - 1) / 2;
	}
	std::cout << res << std::endl;
	return 0;
}