Submission #1145463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145463		arashmemar	Election (BOI18_election)	C++20	100 / 100	1765 ms	124260 KiB

election

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

const int maxn = 5e5 + 100;

int a[maxn];

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

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

	void init()
	{
		if (R - L == 1)
		{
			return ;
		}
		lc = new Node(L, mid);
		rc = new Node(mid, R);
		lc->init();
		rc->init();
		return ;
	}

	void spread()
	{
		v.first += lazy;
		if (lc)
		{
			lc->lazy += lazy;
			rc->lazy += lazy;
		}
		lazy = 0;
		return ;
	}

	void update(int l, int r, int val)
	{
		spread();
		if (L == l and R == r)
		{
			lazy = val;
			spread();
			return ;
		}
		if (l < mid)
		{
			lc->update(l, min(r, mid), val);
		}
		if (r > mid)
		{
			rc->update(max(l, mid), r, val);
		}
		lc->spread();
		rc->spread();
		v = min(lc->v, rc->v);
	}

	pair <int, int> get(int l, int r)
	{
		spread();
		if (l == L and r == R)
		{
			return v;
		}
		pair <int, int> ret = {maxn, 0};
		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;
	}

	pair <int, int> bsss()
	{
		spread();
		if (R - L == 1)
		{
			return v;
		}
		lc->spread();
		rc->spread();
		if (lc->v.first < 0)
		{
			return lc->bsss();
		}
		return rc->bsss();
	}

	pair <int, int> bs(int l, int r)
	{
		spread();	
		if (l >= r or v.first >= 0)
		{
			return {maxn, 0};
		}
		if (l == L and R == r)
		{
			return bsss();
		}
		pair <int, int> tmp = lc->bs(l, min(mid, r));
		if (tmp.second)
		{
			return tmp;
		}
		return rc->bs(max(l, mid), r);
	}
};

vector <pair <int, int>> qs[maxn];

int ans[maxn];

vector <int> bp;

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;
	}

	a[0] = 1;

	Node *lr = new Node(0, n + 1), *rr = new Node(0 , n + 1);

	lr->init();
	rr->init();

	for (int i = 0;i <= n;i++)
	{
		lr->update(i, n + 1, a[i]);
		rr->update(1, i + 1, a[i]);
	}


	int q;
	cin >> q;
	for (int i = 1;i <= q;i++)
	{
		int l, r;
		cin >> l >> r;
		qs[l].push_back({r, i});
	}

	int s = 0;
	for (int i = 0;i <= n;i++)
	{
		s += a[i];
		if (s < 0)
		{
			s++;
			bp.push_back(-i);
			rr->update(1, i + 1, 1);
		}
	}

	reverse(bp.begin(), bp.end());

	for (int i = 1;i <= n;i++)
	{
		lr->update(i, n + 1, -a[i - 1]);

		if (a[i - 1] == -1 and bp.size())
		{
			bp.pop_back();
		}
		if (a[i - 1] == 1)
		{
			int ind = lr->bs(i, n + 1).second;
			if (ind)
			{
				bp.push_back(-ind);
				rr->update(1, ind + 1, 1);
			}
		}

		for (auto o : qs[i])
		{
			int r = o.first, aq = o.second;
			int rans = bp.end() - lower_bound(bp.begin(), bp.end(), -r);
			int ind = rr->get(i, r + 1).second;

			int tmp2 = 0;
			if (r != n)
			{
				tmp2 = rr->get(r + 1, r + 2).first;
			}

			rans += max(0, -rr->get(i, r + 1).first + tmp2);
			ans[aq] = rans;
		}
	}

	for (int i = 1;i <= q;i++)
	{
		cout << ans[i] << '\n';
	}
}

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