Submission #582580

#	Time	Username	Problem	Language	Result	Execution time	Memory
582580		willi19	Election (BOI18_election)	C++17	100 / 100	1765 ms	72252 KiB

election

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

typedef long long ll;
typedef pair<ll,ll> pll;

const ll MX = 1<<19;
const ll INF = 1e18;

#define f first
#define s second

ll n,q,a[MX],ans[MX];
string s;
vector<pll> query[MX];
vector<pll> vec;

template<class T,ll SZ> struct maxtree//with range update
{
	ll mx[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
	maxtree()
	{
		memset(mx,0,sizeof mx);
		memset(lazy,0,sizeof lazy);
	}
	
	void propagate(ll l,ll r, ll ind)
	{
		if(lazy[ind])
		{
			mx[ind] += lazy[ind];
			if(l!=r)
			{
				lazy[ind*2]+=lazy[ind];
				lazy[ind*2+1]+=lazy[ind];
			}
			lazy[ind] = 0;
		}
	}
	
	void pull(ll ind)
	{
		mx[ind] = max(mx[ind*2],mx[ind*2+1]);
	}
	
	T merge(T left,T right)
	{
		return max(left,right);
	}
	
	void update(ll l,ll r,ll s,ll e,ll ind,ll val)
	{
		propagate(l,r,ind);
		if(e<l||r<s)
			return;
		if(s<=l&&r<=e)
		{
			lazy[ind]+=val;
			propagate(l,r,ind);
			return;
		}
		ll mid = (l+r)>>1;
		update(l,mid,s,e,ind*2,val);
		update(mid+1,r,s,e,ind*2+1,val);
		pull(ind);
	}
	
	T query(ll l,ll r,ll s,ll e, ll ind)
	{
		propagate(l,r,ind);
		if(e<l || r<s)
			return -INF;
		if(s<=l&&r<=e)
		{
			//cout<<l<<" "<<r<<" "<<s<<" "<<e<<" "<<ind<<" "<<mx[ind]<<"===\n";
			return mx[ind];
		}
		ll mid = (l+r)>>1;
		return merge(query(l,mid,s,e,ind*2),query(mid+1,r,s,e,ind*2+1));
	}
};

template<class T,ll SZ> struct sumtree//without range update
{
	ll v[2*SZ]; // set SZ to a power of 2
	sumtree()
	{
		memset(v,0,sizeof v);
	}
	
	T merge(T left, T right)
	{
		return left+right;
	}
	
	void update(ll l,ll r,ll x,ll ind,ll val)
	{
		//cout<<l<<" "<<r<<" "<<x<<" "<<ind<<" "<<val<<"\n";
		if(x<l||r<x)
			return;
		if(l==r)
		{
			v[ind]+=val;
			return;
		}
		ll mid = (l+r)>>1;
		update(l,mid,x,ind*2,val);
		update(mid+1,r,x,ind*2+1,val);
		v[ind] = merge(v[ind*2],v[ind*2+1]);
	}
	
	T query(ll l,ll r,ll s,ll e, ll ind)
	{
		//cout<<l<<" "<<r<<" "<<s<<" "<<e<<" "<<ind<<"\n";
		if(e<l || r<s)
			return 0;
		if(s<=l&&r<=e)
			return v[ind];
		ll mid = (l+r)>>1;
		return merge(query(l,mid,s,e,ind*2),query(mid+1,r,s,e,ind*2+1));
	}
};

maxtree<ll, MX> mtree;
sumtree<ll, MX> stree;

void solve(ll x) 
{
	while(vec.size()&&vec.back().f >= a[x])
	{
		stree.update(0,MX-1,vec.back().s,1,-1);
		mtree.update(0,MX-1,vec.back().s,MX-1,1,-1);
		vec.pop_back();
	}
	for(auto z:query[x])
	{
		ll m1 = mtree.query(0,MX-1,x,z.f,1);
		ll m2 = mtree.query(0,MX-1,z.f,z.f,1);
		ans[z.s] = stree.query(0,MX-1,x+1,z.f,1)+m1-m2;
		//cout<<stree.query(0,MX-1,x+1,z.f,1)<<"======"<<m1<<"====="<<m2<<"===="<<x<<"=====\n";
	}
	if(x)
	{
		stree.update(0,MX-1,x,1,1);
		mtree.update(0,MX-1,x,MX-1,1,1);
		vec.push_back({a[x],x});
	}
}


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;
	}
	for(ll i=0;i<n+1;i++)
		mtree.update(0,MX-1,i,i,1,a[i]);
	cin>>q;
	for(ll i=0;i<q;i++)
	{
		ll l,r;
		cin>>l>>r;
		query[l-1].push_back({r,i});
	}
	for(ll i=n;i>=0;i--) solve(i);
	for(ll i=0;i<q;i++)	cout<<ans[i]<<"\n";
}

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