Submission #1311189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311189		LM1	Election (BOI18_election)	C++20	28 / 100	3095 ms	952 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define fr(i,ii,iii) for(int i=ii;i<iii;i++)
const int N=5e5+5;
int n,q,pr[N];
set<int>st;
string a;
void check(int l,int r,int d){
	int x=0;
	if(d==0){
		fr(i,l,r+1){
			if(pr[i]-pr[l-1]<x){
				x--;
				st.insert(i);
			}
		}
	}
	else{
		for(int i=r;i>=l;i--){
			if(st.count(i))x--;
			if(pr[r]-pr[i-1]<x){
				x--;
				st.insert(i);
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>a>>q;
	a='@'+a;
	fr(i,1,n+1){
		pr[i]=pr[i-1]+(a[i]=='C'?1:-1);
	}
	while(q--){
		int l,r;cin>>l>>r;
		st.clear();
		check(l,r,0);
		check(l,r,1);
		cout<<st.size()<<"\n";		
	}
}

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