Submission #534645

#	Time	Username	Problem	Language	Result	Execution time	Memory
534645		GioChkhaidze	Election (BOI18_election)	C++14	100 / 100	469 ms	29408 KiB

election

// Balkan Olympiad in Informatics 2018 - election

#include <bits/stdc++.h>

#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r

using namespace std;

const int N = 5e5 + 5;

int n, q, L, R, a[N];

struct node {
	int pr = 0;
	int sf = 0;
	int sum = 0;
	int ans = 0;
};

node v[4 * N], base;

node comb(node a, node b) {
	node c;
	c.sum = a.sum + b.sum;
	c.pr = max(a.pr, a.sum + b.pr);
	c.sf = max(b.sf, b.sum + a.sf);
	c.ans = max(a.sum + b.ans, a.ans + b.sum);
	c.ans = max(c.ans, a.pr + b.sf);
	return c;
}

void build(tree) {
	if (l == r) {
		v[h].sum = a[l];
		v[h].pr = max(v[h].pr, a[l]);
		v[h].sf = max(v[h].sf, a[l]);
		v[h].ans = max(v[h].ans, a[l]);
		return ;
	}
	build(left), build(right);
	v[h] = comb(v[lf], v[rf]);
}

node get(tree) {
	if (r < L || R < l) return base;
	if (L <= l && r <= R) return v[h];
	return comb(get(left), get(right));
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		char c;
		cin >> c;
		if (c == 'T')
			a[i] = 1;
				else 
			a[i] = -1;
	}
	
	build(1, 1, n);
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		cin >> L >> R;
		cout << get(1, 1, n).ans << "\n";
	}
}

Compilation message (stderr)

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

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