oj.uz

Submission #611851

# Submission time Handle Problem Language Result Execution time Memory
611851 2022-07-29T08:07:30 Z amunduzbaev Election (BOI18_election) C++17
82 / 100
 283 ms 49556 KB 
#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]++;
			if(i + 1 < r) 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;
		}
		mx[1][b]++, mx[0][b]++;
		for(int i=mx[0][b] - 1;i>0;i--){
			int cc = 0, r = i;
			for(int j=mx[1][b] - 1;j>0;j--){
				while(r < mx[0][b] && pos[b][r] < sos[b][j]) r++;
				if(r < mx[0][b]) 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;
		}
		
		//~ cout<<l<<" "<<(l_ + 1) * B - 1<<" <-\n";
		int sum = 0, x = 1, cnt = 0;
		for(int i=l;i<(l_ + 1) * B;i++){
			if(s[i] == 'C') sum--;
			else sum++;
			//~ cout<<i<<" "<<sum<<" "<<x<<"\n";
			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;
			else pv[b] = mx[0][b];
			//~ cout<<b<<" "<<mx[0][b]<<" "<<pv[b]<<" <-\n";
			x += (mx[0][b] - pv[b]);
			cnt += (mx[0][b] - pv[b]);
			sum += suff[b * B];
		}
		for(int i=r_ * B;i<=r;i++){
			if(s[i] == 'C') sum--;
			else sum++;
			//~ cout<<i<<" "<<sum<<" "<<x<<"\n";
			if(sum == x) used[i] = 1, cnt++, x++;
		}
		//~ cout<<cnt<<" : ";
		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++;
			}
		}
		//~ cout<<cnt<<" : ";
		for(int b=r_-1;b>l_;b--){
			if(mx[1][b] > x - sum){
				sv[b] = x - sum;
				x += (mx[1][b] - x + sum);
			} else {
				sv[b] = mx[1][b];
			}
			
			is += in[b][pv[b]][sv[b]];
			//~ cout<<is<<" "<<mx[1][b]<<" "<<sv[b]<<"\n";
			cnt += max(0, mx[1][b] - sv[b] - is);
			is -= min(is, mx[1][b] - sv[b]);
			
			is += (mx[0][b] - pv[b] - in[b][pv[b]][sv[b]]);
			sum += suff[b * B];
		}
		//~ cout<<cnt<<" : ";
		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++;
			}
		}
		
		cout<<cnt<<"\n";
	}
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 219 ms 7492 KB Output is correct
7 Correct 273 ms 6952 KB Output is correct
8 Correct 221 ms 6908 KB Output is correct
9 Correct 131 ms 7116 KB Output is correct
10 Correct 216 ms 3792 KB Output is correct
11 Correct 283 ms 19288 KB Output is correct
12 Correct 144 ms 37888 KB Output is correct
13 Correct 139 ms 49556 KB Output is correct
14 Correct 153 ms 34308 KB Output is correct
15 Correct 118 ms 22520 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 219 ms 7492 KB Output is correct
7 Correct 273 ms 6952 KB Output is correct
8 Correct 221 ms 6908 KB Output is correct
9 Correct 131 ms 7116 KB Output is correct
10 Correct 216 ms 3792 KB Output is correct
11 Correct 283 ms 19288 KB Output is correct
12 Correct 144 ms 37888 KB Output is correct
13 Correct 139 ms 49556 KB Output is correct
14 Correct 153 ms 34308 KB Output is correct
15 Correct 118 ms 22520 KB Output is correct
16 Runtime error 15 ms 13868 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -