Submission #679273

#	Time	Username	Problem	Language	Result	Execution time	Memory
679273		gyandevrey6	Election (BOI18_election)	C++17	0 / 100	13 ms	31572 KiB

election

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
//1 => l-1~r 
ll n,q,a[500100];
string s;
 
typedef struct leaf{
	ll minind,maxind;
}leaf;
 
vector<leaf> tree = vector<leaf>(2000100);
 
void init(ll l,ll r,ll ind)
{
	if(l==r)
	{
		tree[ind].minind = tree[ind].maxind = l;
		return;
	}
	init(l,(l+r)/2,ind*2);
	init((l+r)/2+1,r,ind*2+1);
	tree[ind].minind = a[tree[ind*2].minind]>=a[tree[ind*2+1].minind]?tree[ind*2+1].minind:tree[ind*2].minind;
	tree[ind].maxind = a[tree[ind*2].maxind]<=a[tree[ind*2+1].maxind]?tree[ind*2+1].maxind:tree[ind*2].maxind;
}
 
leaf query(ll l,ll r,ll s,ll e,ll ind)
{
	if(s<=l&&r<=e)
		return tree[ind];
	if(e<l||r<s)
	{
		leaf ret;
		ret.minind = ret.maxind = -1;
		return ret;
	}
	leaf r1=query(l,(l+r)/2,s,e,ind*2);
	leaf r2=query((l+r)/2+1,r,s,e,ind*2+1);
	leaf ret;
	if(r1.minind==-1)
		return r2;
	if(r2.minind==-1)
		return r1;
	ret.minind = a[r1.minind]>=a[r2.minind]?r2.minind:r1.minind;
	ret.maxind = a[r1.maxind]<=a[r2.maxind]?r2.maxind:r1.maxind;
	return ret;
}
 
ll ans(ll l,ll r)
{
	leaf t = query(0,n,l,r,1);
	ll b = a[t.maxind]-a[r];
	ll av = a[l]-a[t.minind];
	leaf t2 = query(0,n,l,t.maxind,1);
	leaf t3 = query(0,n,t.minind,r,1);
	ll c = a[l]-a[t2.minind];
	ll d = a[t3.maxind]-a[r];
	
	return c+d+max(b-d,av-c);
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	cin>>s;
	for(ll i=0;i<n;i++)
	{
		if(s[i]=='C')
			a[i+1] = a[i]+1;
		else
			a[i+1] = a[i]-1;
	}
	init(0,n,1);
	cin>>q;
	while(q--)
	{
		ll l,r;
		cin>>l>>r;
		cout<<ans(l-1,r)<<"\n";
	}
}

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