Submission #1145269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145269		arashmemar	Election (BOI18_election)	C++20	0 / 100	2 ms	832 KiB

election

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 100;

int a[maxn];

struct Nodemx
{
	int L, R, mid;
	pair <int, int> v;
	Nodemx *lc, *rc;

	Nodemx(int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, v = {0, 0}, lc = rc = NULL;
		return ;
	}

	void init()
	{
		if (R - L == 1)
		{
			v = {a[L], L};
			return ;
		}
		lc = new Nodemx(L, mid);
		rc = new Nodemx(mid, R);
		lc->init();
		rc->init();
		v = max(lc->v, rc->v);
		return ;
	}

	pair <int, int> get(int l, int r)
	{
		if (L == l and r == R)
		{
			return v;
		}
		pair <int, int> ret = {-maxn, 0};
		if (l < mid)
		{
			ret = max(ret, lc->get(l, min(r, mid)));
		}
		if (r > mid)
		{
			ret = max(ret, rc->get(max(l, mid), r));
		}
		return ret;
	}
};

struct Nodemn
{
	int L, R, mid, v;
	Nodemn *lc, *rc;

	Nodemn(int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, v = 0, lc = rc = NULL;
		return ;
	}

	void init()
	{
		if (R - L == 1)
		{
			v = a[L];
			return ;
		}
		lc = new Nodemn(L, mid);
		rc = new Nodemn(mid, R);
		lc->init();
		rc->init();
		v = min(lc->v, rc->v);
		return ;
	}

	int get(int l, int r)
	{
		if (l >= r)
		{
			return 0;
		}
		if (L == l and r == R)
		{
			return v;
		}
		int ret = maxn;
		if (l < mid)
		{
			ret = min(ret, lc->get(l, min(r, mid)));
		}
		if (r > mid)
		{
			ret = min(ret, rc->get(max(l, mid), r));
		}
		return ret;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n;i++)
	{
		char inp;
		cin >> inp;
		a[i] = (inp == 'C') * 2 - 1;
	}
	for (int i = 1;i <= n;i++)
	{
		a[i] += a[i - 1];
	}
	Nodemn *rootmn = new Nodemn(0, n + 1);
	rootmn->init();
	Nodemx *rootmx = new Nodemx(0, n + 1);
	rootmx->init();

	int q;
	cin >> q;
	while (q--)
	{
		int l, r;
		cin >> l >> r;
		pair <int, int> tmp = rootmx->get(l - 1, r + 1);
		int ind = tmp.second, val = tmp.first;
		int ans = 0;
		ans += abs(min(rootmn->get(l, ind) - a[l - 1], 0));
		ans += max(max(val - a[r], 0), max(0, abs(rootmn->get(ind + 1, r + 1)) + a[l - 1] - ans));
		cout << ans << '\n';
	}
}

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