結果

問題 No.346 チワワ数え上げ問題
ユーザー yudedako
提出日時 2016-03-01 17:02:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 1,342 bytes
コンパイル時間 596 ms
コンパイル使用メモリ 68,328 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-24 13:08:25
合計ジャッジ時間 1,465 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0