Submission #611801

#	Time	Username	Problem	Language	Result	Execution time	Memory
611801		amunduzbaev	Election (BOI18_election)	C++17	28 / 100	3063 ms	57868 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]];
			//~ cnt += max(0, mx[1][b] - sv[b] + 1 - is);
			//~ is -= min(is, mx[1][b] - sv[b] + 1);
			
			//~ 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";
	}
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:52:7: warning: unused variable 'l_' [-Wunused-variable]
   52 |   int l_ = l / B, r_ = r / B;
      |       ^~
election.cpp:52:19: warning: unused variable 'r_' [-Wunused-variable]
   52 |   int l_ = l / B, r_ = r / B;
      |                   ^~

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