Submission #584346

#	Time	Username	Problem	Language	Result	Execution time	Memory
584346		codr0	Election (BOI18_election)	C++14	100 / 100	547 ms	27952 KiB

election

// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define bit(i,j) ((j>>i)&1)
#define minm(x,y) x=min(x,y)
#define maxm(x,y) x=max(x,y)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n'
#define wtf cout<<"WHAT THE FUCK!\n"
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1

using namespace std;
const int N=5e5+4;
struct node{
	int sum,pr,sf,ans;
};
node seg[4*N];
node emp;

	node merge(node a,node b){
		node rt;
		rt.sum=a.sum+b.sum;
		rt.pr=max(a.pr,a.sum+b.pr);
		rt.sf=max(a.sf+b.sum,b.sf);
		rt.ans=max(a.ans+b.sum,b.ans+a.sum);
		maxm(rt.ans,a.pr+b.sf);
		return rt;
	}

	void upd(int id,int l,int r,int ind,int x){
		if(l>ind||r<=ind) return;
		if(l+1==r){
			seg[id].ans=max(0,x);
			seg[id].sf=max(0,x);
			seg[id].pr=max(0,x);
			seg[id].sum=x;
			return;
		}
		dmid;
		upd(lc,l,mid,ind,x);
		upd(rc,mid,r,ind,x);
		seg[id]=merge(seg[lc],seg[rc]);
	}

	node get(int id,int l,int r,int st,int en){
		if(st>=r||en<=l) return emp;
		if(st<=l&&en>=r) return seg[id];
		dmid;
		return merge(get(lc,l,mid,st,en),get(rc,mid,r,st,en));
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);	

	int n; cin>>n;
	string s; cin>>s;
	s='$'+s;
	FOR(i,1,n){
		if(s[i]=='C') upd(1,1,n+1,i,-1);
		else upd(1,1,n+1,i,+1);
	}
	int q; cin>>q;
	while(q--){
		int l,r; cin>>l>>r;
		cout<<get(1,1,n+1,l,r+1).ans<<'\n';
	}

	return 0;
    }

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