Submission #611799

#	Time	Username	Problem	Language	Result	Execution time	Memory
611799		amunduzbaev	Election (BOI18_election)	C++17	0 / 100	4 ms	724 KiB

election

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define her cerr<<"here"<<endl;

const int N = 7e5 + 5;
const int B = 267;
int a[N], pref[N], suff[N], mx[2][B + 1], in[B][B + 1][B + 1];
int pos[B][B + 1], sos[B][B + 1], used[N];
int pv[B], sv[B];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	string s; cin >> s;
	
	for(int b=0;b * B<n;b++){
		int l = b * B, r = min(n, (b + 1) * B);
		memset(pos[b], -1, sizeof pos[b]);
		for(int i=l;i<r;i++){
			if(s[i] == 'C') pref[i]--;
			else pref[i]++;
			pref[i + 1] = pref[i];
			mx[0][b] = max(mx[0][b], pref[i]);
			if(pref[i] > 0 && pos[b][pref[i]] == -1) pos[b][pref[i]] = i;
		}
		
		memset(sos[b], -1, sizeof sos[b]);
		for(int i=r-1;i>=l;i--){
			suff[i] = suff[i + 1];
			if(s[i] == 'C') suff[i]--;
			else suff[i]++;
			mx[1][b] = max(mx[1][b], suff[i]);
			if(suff[i] > 0 && sos[b][suff[i]] == -1) sos[b][suff[i]] = i;
		}
		for(int i=mx[0][b];i>0;i--){
			int cc = 0, r = mx[0][b];
			for(int j=mx[1][b];j>0;j--){
				if(r > 0 && sos[b][j] <= pos[b][r]) cc++, r--;
				in[b][i][j] = cc;
			}
		}
	}
	int q; cin >> q;
	for(int i=0;i<q;i++){
		int l, r; cin >> l >> r;
		l--, r--;
		int l_ = l / B, r_ = r / B;
		if(l_ == r_){
			int sum = 0, x = 1, cnt = 0;
			for(int i=l;i<=r;i++){
				if(s[i] == 'C') sum--;
				else sum++;
				if(sum == x) used[i] = 1, cnt++, x++;
			}
			int is = 0; sum = 0, x = 1;
			for(int i=r;i>=l;i--){
				if(s[i] == 'C') sum--;
				else sum++;
				if(used[i]) is++, used[i] = 0;
				if(sum == x){
					if(!is) cnt++;
					else is--;
					x++;
				}
			}
			
			cout<<cnt<<"\n";
			for(int i=l;i<=r;i++) used[i] = 0;
			continue;
		}
		
		int sum = 0, x = 1, cnt = 0;
		for(int i=l;i<(l_ + 1) * B;i++){
			if(s[i] == 'C') sum--;
			else sum++;
			if(sum == x) used[i] = 1, cnt++, x++;
		}
		
		for(int b=l_+1;b<r_;b++){
			if(mx[0][b] >= x - sum){
				pv[b] = x - sum;
				x += (mx[0][b] - x + sum + 1);
			} else {
				pv[b] = mx[0][b] + 1;
			}
			
			sum += suff[b * B];
		}
		for(int i=r_ * B;i<=r;i++){
			if(s[i] == 'C') sum--;
			else sum++;
			if(sum == x) used[i] = 1, cnt++, x++;
		}
		
		int is = 0;
		sum = 0, x = 1;
		for(int i=r;i>=r_*B;i--){
			if(s[i] == 'C') sum--;
			else sum++;
			if(used[i]) is++, used[i] = 0;
			if(sum == x){
				if(!is) cnt++;
				else is--;
				x++;
			}
			used[i] = 0;
		}
		
		for(int b=r_-1;b>l_;b--){
			if(mx[1][b] >= x - sum){
				sv[b] = x - sum;
				x += (mx[1][b] - x + sum + 1);
			} else {
				sv[b] = mx[1][b] + 1;
			}
			
			cnt += mx[0][b] - pv[b] + 1; // in[b][pv[b]][sv[b]];
			is += in[b][pv[b]][sv[b]];
			if(is >= (mx[1][b] - sv[b] + 1)) is -= (mx[1][b] - sv[b] + 1);
			else {
				cnt += (mx[1][b] - sv[b] + 1 - is);
				is = 0;
			}
			
			is += (mx[0][b] - pv[b] + 1 - in[b][pv[b]][sv[b]]);
			sum += suff[b * B];
		}
		
		for(int i=(l_ + 1) * B - 1;i>=l;i--){
			if(s[i] == 'C') sum--;
			else sum++;
			if(used[i]) is++, used[i] = 0;
			if(sum == x){
				if(!is) cnt++;
				else is--;
				x++;
			}
			
			used[i] = 0;
		}
		
		cout<<cnt<<"\n";
	}
}

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