oj.uz

Submission #582580

# Submission time Handle Problem Language Result Execution time Memory
582580 2022-06-24T06:20:18 Z willi19 Election (BOI18_election) C++17
100 / 100
 1765 ms 72252 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37244 KB Output is correct
2 Correct 29 ms 37260 KB Output is correct
3 Correct 24 ms 37332 KB Output is correct
4 Correct 27 ms 37332 KB Output is correct
5 Correct 28 ms 37260 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37244 KB Output is correct
2 Correct 29 ms 37260 KB Output is correct
3 Correct 24 ms 37332 KB Output is correct
4 Correct 27 ms 37332 KB Output is correct
5 Correct 28 ms 37260 KB Output is correct
6 Correct 222 ms 41460 KB Output is correct
7 Correct 210 ms 41396 KB Output is correct
8 Correct 204 ms 41160 KB Output is correct
9 Correct 238 ms 41340 KB Output is correct
10 Correct 211 ms 41348 KB Output is correct
11 Correct 210 ms 41852 KB Output is correct
12 Correct 206 ms 41680 KB Output is correct
13 Correct 200 ms 42124 KB Output is correct
14 Correct 218 ms 41840 KB Output is correct
15 Correct 237 ms 41448 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37244 KB Output is correct
2 Correct 29 ms 37260 KB Output is correct
3 Correct 24 ms 37332 KB Output is correct
4 Correct 27 ms 37332 KB Output is correct
5 Correct 28 ms 37260 KB Output is correct
6 Correct 222 ms 41460 KB Output is correct
7 Correct 210 ms 41396 KB Output is correct
8 Correct 204 ms 41160 KB Output is correct
9 Correct 238 ms 41340 KB Output is correct
10 Correct 211 ms 41348 KB Output is correct
11 Correct 210 ms 41852 KB Output is correct
12 Correct 206 ms 41680 KB Output is correct
13 Correct 200 ms 42124 KB Output is correct
14 Correct 218 ms 41840 KB Output is correct
15 Correct 237 ms 41448 KB Output is correct
16 Correct 1765 ms 68684 KB Output is correct
17 Correct 1566 ms 67640 KB Output is correct
18 Correct 1691 ms 66572 KB Output is correct
19 Correct 1652 ms 67620 KB Output is correct
20 Correct 1756 ms 67608 KB Output is correct
21 Correct 1620 ms 71548 KB Output is correct
22 Correct 1578 ms 70292 KB Output is correct
23 Correct 1669 ms 72252 KB Output is correct
24 Correct 1609 ms 70644 KB Output is correct
25 Correct 1571 ms 69160 KB Output is correct