제출 #1131169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131169		xnqs	Election (BOI18_election)	C++20	82 / 100	685 ms	19376 KiB

election

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

struct SegTreeNode {
	int sum = 0;
	int max_pfx = 0;
	int max_sfx = 0;
	int max = 0;
};

SegTreeNode combine(const SegTreeNode& a, const SegTreeNode& b) {
	SegTreeNode ret;
	ret.sum = a.sum + b.sum;
	ret.max_pfx = std::max({0, a.max_pfx, a.sum + b.max_pfx});
	ret.max_sfx = std::max({0, b.max_sfx, b.sum + a.max_sfx});
	ret.max = std::max({0, a.max + b.sum, b.max + a.sum, a.max_pfx + b.max_sfx});
	return ret;
}

int x, q;
std::string str;
SegTreeNode tree[2000005];

void build_tree(int node, int l, int r) {
	if (l==r) {
		tree[node].sum = ((str[l]=='C') ? -1 : 1);
		tree[node].max_pfx = tree[node].max_sfx = tree[node].sum;
		tree[node].max = std::max(0, tree[node].sum);
		return;
	}

	int m = (l+r)>>1;
	build_tree(node<<1,l,m);
	build_tree(node<<1|1,m+1,r);
	tree[node] = combine(tree[node<<1],tree[node<<1|1]);
}

SegTreeNode query(int node, int l, int r, int st, int fi) {
	if (l>fi||r<st) {
		SegTreeNode ret;
		return ret;
	}
	if (st<=l&&r<=fi) {
		return tree[node];
	}

	int m = (l+r)>>1;
	return combine(query(node<<1,l,m,st,fi),query(node<<1|1,m+1,r,st,fi));
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> str;
	build_tree(1,0,x-1);

	std::cin >> q;
	while (q--) {
		int l, r;
		std::cin >> l >> r; --l, --r;

		SegTreeNode ret = query(1,0,x-1,l,r);
		//std::cout << ret.sum << " " << ret.max_pfx << " " << ret.max_sfx << " " << ret.max << "\n";
		std::cout << query(1,0,x-1,l,r).max << "\n";
	}
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 0 / 18