Submission #647046

#	Time	Username	Problem	Language	Result	Execution time	Memory
647046		42kangaroo	Election (BOI18_election)	C++17	0 / 100	3 ms	468 KiB

election

//
// Created by 42kangaroo on 01/10/2022.
//

#include "bits/stdc++.h"

using namespace std;

#define int long long

struct Val {
	int CTDif, l, r, nul;

};

Val combine(const Val& l, const Val& r) {
	Val res{l.CTDif + r.CTDif, l.l + max((int)0,r.l - max((int)0, (l.CTDif + l.l))),r.r +max((int)0, l.r -  max((int)0,(r.CTDif + r.r))), 0};
	res.nul = max(l.l + r.r, max(res.l, res.r));
	return res;
}

pair<vector<bool>, int> input(){
	int n, q;
	cin  >> n;
	vector<bool> fans(n);
	for (auto&& f: fans) {
		char c;
		cin >> c;
		f = c == 'C';
	}
	cin >> q;
	return {fans, q};
}

struct SegTe {
	vector<Val> cache_;

	Val build(int l, int r, int i, const vector<bool>& inputVec) {
		if (l+1 >= r) return cache_[i] = (inputVec[l] ? Val{1, 0 ,0, 0} : Val{-1, 1, 1, 1} );
		int m = (l + r) / 2;
		return cache_[i] = combine(build(l , m, 2*i+1, inputVec), build(m,r, 2*i+2, inputVec));
	}

	Val get(int l, int r, int i, int ql, int qr) {
		if (qr <= l || ql >= r) return {0,0,0, 0};
		if (ql <= l && qr >= r) return cache_[i];
		int m = (l+r)/2;
		return combine(get(l,m, 2*i+1, ql, qr), get(m,r,2*i+2, ql, qr));
	}

	SegTe(const vector<bool>& inputVec): cache_(inputVec.size()*4){
		build(0, inputVec.size(), 0, inputVec);
	}
};

signed main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
    auto [fans, q] = input();
	SegTe tree{fans};
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		cout << tree.get(0 ,fans.size(), 0 ,l-1, r).nul << "\n";
	}
}

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