Submission #707369

#	Time	Username	Problem	Language	Result	Execution time	Memory
707369		KLPP	Election (BOI18_election)	C++14	100 / 100	688 ms	136804 KiB

election

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

class ST{
	vector<array<lld,4>>arr;
	public:
	void init(int n){
		arr.resize(8*n,{0,0,0});
	}
	array<lld,4> combine(array<lld,4> A, array<lld,4> B){
		array<lld,4> C={A[0]+B[0],max(A[1],A[0]+B[1]),max(B[2],B[0]+A[2]),max(A[3],max(B[3],A[2]+B[1]))};
		return C;
	}
	void update(int a, int b, int node, int pos, lld val){
		if(pos<a || b<pos)return;
		if(a==b){
			arr[node]={val,max(0LL,val),max(0LL,val),max(0LL,val)};
			return;
		}
		int mid=(a+b)/2;
		update(a,mid,2*node,pos,val);
		update(mid+1,b,2*node+1,pos,val);
		arr[node]=combine(arr[2*node],arr[2*node+1]);
	}
	array<lld,4> query(int a, int b, int node, int l, int r){
		if(r<a || b<l){
			return {0,0,0,0};
		}
		if(l<=a && b<=r){
			return arr[node];
		}
		int mid=(a+b)/2;
		return combine(query(a,mid,2*node,l,r),query(mid+1,b,2*node+1,l,r));
	}
};

void solve(){
	/*freopen("cardgame.in", "r", stdin);
	freopen("cardgame.out", "w", stdout);*/
	int n,q;
	cin>>n;
	string s;
	cin>>s;
	cin>>q;
	ST S;
	S.init(n);
	rep(i,0,n){
		if(s[i]=='C')S.update(0,n-1,1,i,1);
		else S.update(0,n-1,1,i,-1);
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		l--;r--;
		array<lld,4> A=S.query(0,n-1,1,l,r);
		cout<<A[3]-A[0]<<"\n";
	}
}
	

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.precision(16);
	int tt=1;
	//cin>>tt;
	rep(test,0,tt){
		solve();
	}
}

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