Submission #362066

#	Time	Username	Problem	Language	Result	Execution time	Memory
362066		kshitij_sodani	Election (BOI18_election)	C++14	100 / 100	1666 ms	66220 KiB

election

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


llo n;
llo it[500001];
vector<pair<llo,llo>> qq[500001];
llo ans[500001];
llo pre[500001];
llo tree[4*500001];
llo lazy[4*500001];
void push(llo no,llo l,llo r){
	tree[no]+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
}
void update(llo no,llo l,llo r,llo aa,llo bb,llo cc){
	push(no,l,r);
	if(l>bb or r<aa){
		return;
	}
	if(aa<=l and r<=bb){
		lazy[no]+=cc;
		push(no,l,r);
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,cc);
		update(no*2+2,mid+1,r,aa,bb,cc);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}

}
llo query(llo no,llo l,llo r,llo aa,llo bb){
	push(no,l,r);
	if(r<aa or l>bb){
		return -1e9;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		llo mid=(l+r)/2;
		llo x=query(no*2+1,l,mid,aa,bb);
		llo y=query(no*2+2,mid+1,r,aa,bb);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
		return max(x,y);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	string s;
	cin>>s;
	for(llo i=0;i<n;i++){
		if(s[i]=='T'){
			it[i]=-1;
		}
		else{
			it[i]=1;
		}
		pre[i+1]=pre[i]+it[i];
		//cout<<it[i]<<",";
	}

	//cout<<endl;
	llo q;
	cin>>q;
	for(llo ii=0;ii<q;ii++){
		llo l,r;
		cin>>l>>r;
		l--;
		r--;
		qq[l].pb({r,ii});
		continue;
		llo su=0;
		vector<llo> kk;
		for(llo i=l;i<=r;i++){
			kk.pb(it[i]);
		}
		llo ans=0;
		for(llo i=0;i<kk.size();i++){
			su+=kk[i];
			if(su<0){
				su-=kk[i];
				kk[i]=0;
				ans++;
			}
		}
		su=0;
		for(llo i=kk.size()-1;i>=0;i--){
			su+=kk[i];
			if(su<0){
				su-=kk[i];
				kk[i]=0;
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	vector<llo> ss;
	for(llo i=n-1;i>=0;i--){
		update(0,0,n,i+1,n,it[i]);
		if(it[i]==-1){
			update(0,0,n,i+1,n,-it[i]);
			ss.pb(i);
		}
		else{
			if(ss.size()){
				update(0,0,n,ss.back()+1,n,it[ss.back()]);
				ss.pop_back();
			}
		}
		for(auto j:qq[i]){
			ans[j.b]=0;
			if(ss.size()){
				if((ss.back())>j.a){

				}
				else{
					llo ind=ss.size()-1;
					for(llo k=19;k>=0;k--){
						if(ind-(1<<k)>=0){
							if(ss[ind-(1<<k)]<=j.a){
								ind-=(1<<k);
							}
						}
					}
					ans[j.b]+=ss.size()-ind;
				}
			}
			ans[j.b]+=max(-(query(0,0,n,j.a+1,j.a+1)-query(0,0,n,i,j.a+1)),(llo)0);
		}
	}
	for(llo i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}



 
	return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:93:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(llo i=0;i<kk.size();i++){
      |               ~^~~~~~~~~~

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