Submission #1147908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147908		alir3za_zar3	Election (BOI18_election)	C++20	100 / 100	1453 ms	222184 KiB

election

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+7;
int n,q; string s;

struct segment_Tree 
{
	vector<int> erase[N<<2];
	vector<pair<int,int>> erasList[N<<2];
	int T[N<<2][3] , sv[N<<2]; bool mrk[N];

	void wipe_Data ()
	{
		for (int i=0; i<(N<<2); i++)
			T[i][0]=T[i][1]=T[i][2]=sv[i]=0;
		memset(mrk,0,sizeof(mrk));
	}

	void calc_erase (int nd , int l , int r)
	{
		for (int i=l; i<=r; i++) mrk[i] = false;
		for (int i=l; i<=r; i++)
		{
			if (s[i] == 'C') T[nd][0]++;
			else if (T[nd][0] > 0) T[nd][0]--;
			else
			{
				mrk[i] = true;
				erase[nd].push_back(i);
			} 
		}
		for (int i=r; i>=l; i--)
		{
			if (s[i] == 'C') T[nd][1]++;
			else if (T[nd][1] > 0) T[nd][1]--;
			else T[nd][2]++;
		}
		int out = 0 , k = 0;
		for (int i=r; i>=l; i--)
		{
			if (mrk[i])
			{
				erasList[nd].push_back({out,k});
				continue;
			}
			if (s[i] == 'C') k++;
			else if (k > 0) k--;
			else out++;
		}
		reverse(erasList[nd].begin(),erasList[nd].end());
	}

	void build (int nd , int l , int r)
	{
		if (l == r)
		{
			calc_erase(nd , l , r);
			return;
		}
		int m = l+r >> 1;
		build(nd<<1 , l , m);
		build((nd<<1)+1 , m+1 , r);
		calc_erase(nd , l , r);
	}

	pair<int,int> NOerase_ouT (int nd , int l , int r , int lq , int rq , int k)
	{
		if (lq<=l and r<=rq) 
		{
			sv[nd] = erase[nd].size();
			if (sv[nd] > k) sv[nd] -= k , k = 0;
			else k -= sv[nd] , sv[nd] = 0;
			return {sv[nd] , k+T[nd][0]};
		}
		if (r<lq or l>rq) return {0,k};
		int m = l+r >> 1;
		auto [el,kl] = NOerase_ouT(nd<<1 , l , m , lq , rq , k);
		sv[nd] = el , k = kl;
		auto [er,kr] = NOerase_ouT((nd<<1)+1 , m+1 , r , lq , rq , k);
		sv[nd] += er; k = kr;
		return {sv[nd] , k};
	}

	pair<int,int> rv_NOerase_ouT (int nd , int l , int r , int lq , int rq , int k)
	{
		if (lq<=l and r<=rq) 
		{
			int e = T[nd][2];
			if (e > k) e -= k , k = 0;
			else k -= e , e = 0;
			return {e , k+T[nd][1]};
		}
		if (r<lq or l>rq) return {0,k};
		int m = l+r >> 1 , e = 0;
		auto [er,kr] = rv_NOerase_ouT((nd<<1)+1 , m+1 , r , lq , rq , k);
		e = er , k = kr;
		auto [el,kl] = rv_NOerase_ouT(nd<<1 , l , m , lq , rq , k);
		e += el , k = kl;
		return {e , k};
	}

	pair<int,int> rv_optimize (int nd , int l , int r , int lq , int rq , int k)
	{
		int m = l+r >> 1 , e = 0;
		if (lq<=l and r<=rq) 
		{
			int sz = erase[nd].size() , rlimit;
			if (sv[nd] == 0) rlimit = r;
			else rlimit = erase[nd][sz-sv[nd]]-1;
			if (rlimit >= l)
			{
				if (sv[nd] > 0)
				{
					auto [er,kr] = erasList[nd][sz-sv[nd]];
					if (er >= k) e=er-k , k=kr;
					else k -= er-kr ;
				}
				auto [el,kl] = rv_NOerase_ouT(nd , l , r , l , rlimit , k);
				e += el , k = kl;
				return {e , k};
			}
			else {
				e = erasList[nd][0].first;
				if (e >= k) e-=k , k=0;
				else k-=e , e=0;
				k += erasList[nd][0].second;
				return {e , k};
			}
		}
		if (r<lq or l>rq) return {0,k};
		auto [er,kr] = rv_optimize((nd<<1)+1 , m+1 , r , lq , rq , k);
		e += er , k = kr;
		auto [el,kl] = rv_optimize(nd<<1 , l , m , lq , rq , k);
		e += el , k = kl;
		return {e , k};
	}
} sT;

void iN ()
{
	cin >> n >> s >> q;
	   s = 'T' + s;
}

void ouT ()
{
	while (q--)
	{
		int l,r; cin >> l >> r;
		int out = sT.NOerase_ouT(1,1,n,l,r,0).first;
		out += sT.rv_optimize(1,1,n,l,r,0).first;
		cout << out << '\n';
	}
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);

    iN ();
	sT.wipe_Data();
	sT.build(1,1,n);
	ouT ();
}

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