Submission #564241

#	Time	Username	Problem	Language	Result	Execution time	Memory
564241		keta_tsimakuridze	Election (BOI18_election)	C++11	0 / 100	4 ms	468 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int sf[N], p[N], n;
pii tree[4 * N][2];
void build(int u, int l,int r) {
	if(l == r) {
		int i = l;
		tree[u][0] = {p[l], l}; tree[u][1] = {sf[i], i};
		return;
	}
	int mid = (l + r) /2 ;
	build(2 * u, l, mid); build(2 * u + 1, mid + 1,r);
	for(int t = 0; t < 2; t++) tree[u][t] = min(tree[2 * u][t], tree[2 * u + 1][t]);
}
pair<int,int> get(int u,int st,int en, int l,int r, int t) {
	if(l > en || r < st) return {N, 0};
	if(st <= l && r <= en) return tree[u][t];
	int mid = (l + r) / 2;
	return min(get(2 * u, st, en, l, mid, t), get(2 * u + 1, st,en, mid + 1, r, t));
}
pair<int,int> get(int l, int r, int t) {
	pii x = get(1, l, r, 1, n, t);
	if(t) x.f -= sf[r + 1]; else x.f -= p[l - 1];
	if(x.f >= 0) {
		if(t) x = {0, r + 1};
		else x = {0, l - 1};
	} else x.f *= -1;
	return x;
}
main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//	int  p = 0;
	cin >> n;
	string s;
	cin >> s;
	s = '#' + s;
	for(int i = 1; i <= n; i++) {
		p[i] = p[i - 1];
		p[i] += (s[i] == 'C' ? 1 : -1);	
	}
	for(int i = n; i >= 1; i--) {
		sf[i] = sf[i + 1];
		sf[i] += (s[i] == 'C' ? 1 : -1);
	}
	build(1, 1, n);
	int q;
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		pii x = get(l, r, 0), y = get(l, r, 1);
		if(x.s < y.s) cout << x.f + y.f << endl;
		else {
			int b = min(x.f - get(l, y.s - 1, 0).f, y.f - get(x.s + 1, r, 1).f);
			cout << x.f + y.f - b << endl;
		}
		 
	}
}

Compilation message (stderr)

election.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main() {
      | ^~~~

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