Submission #591649

#	Time	Username	Problem	Language	Result	Execution time	Memory
591649		blue	Election (BOI18_election)	C++17	100 / 100	713 ms	63808 KiB

election

#include <iostream>
#include <vector>
using namespace std;
 
using vi = vector<int>;
 
const int inf = 1'000'000'000;

vi p, s;

struct sdata
{
	int pmx = -inf;
	int smx = -inf;
	int ans = -inf;
};

sdata combine(sdata a, sdata b)
{
	return {max(a.pmx, b.pmx), max(a.smx, b.smx), max(max(a.ans, b.ans), a.pmx + b.smx)};
}

struct segtree
{
	int l;
	int r;
	sdata v;

	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{	
		;
	}

	segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r)
			v = sdata{p[l], s[l], p[l]+s[l]};
		else
		{
			int m = (l+r)/2;
			left = new segtree(l, m);
			right = new segtree(m+1, r);
			v = combine(left->v, right->v);
		}
	}

	sdata getrange(int L, int R)
	{
		if(L <= l && r <= R)
			return v;
		else if(R <= (l+r)/2)
			return left->getrange(L, R);
		else if(L >= (l+r)/2+1)
			return right->getrange(L, R);
		else
			return combine(left->getrange(L, R), right->getrange(L, R));
	}
};
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int N;
	cin >> N;
 
	vi A(1+N);
	for(int i = 1; i <= N; i++)
	{
		char c;
		cin >> c;
 
		if(c == 'T')
			A[i] = +1;
		else
			A[i] = -1;
	}
 
	p = vi(1+N);
	p[0] = 0;
	for(int i = 1; i <= N; i++)
		p[i] = p[i-1] + A[i];
 
	s = vi(1+N);
	s[N] = 0;
	for(int i = N-1; i >= 0; i--)
		s[i] = s[i+1] + A[i+1];

	segtree ST(0, N);
 
 
 
	int Q;
	cin >> Q;
 
	for(int q = 1; q <= Q; q++)
	{
		int l, r;
		cin >> l >> r;

		sdata d = ST.getrange(l-1, r);
 
		int pmx = d.pmx;
 
		int c1 = pmx - p[l-1];
 
		// cerr << "c1 = " << c1 << '\n';
		// cerr << "pmx = " << pmx << '\n';
 
 
		// int c2 = 0;
		int res = +s[r] + p[l-1];

		res = max(res, d.ans);
 
 
		res -= s[r] + p[l-1];

		res = max(res, c1);
 
		cout << res << '\n';
 
 
	}
}

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