oj.uz

Submission #611867

# Submission time Handle Problem Language Result Execution time Memory
611867 2022-07-29T08:12:31 Z amunduzbaev Election (BOI18_election) C++17
82 / 100
 3000 ms 42352 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define her cerr<<"here"<<endl;

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

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 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 724 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 237 ms 6364 KB Output is correct
7 Correct 300 ms 5828 KB Output is correct
8 Correct 227 ms 5876 KB Output is correct
9 Correct 133 ms 6212 KB Output is correct
10 Correct 175 ms 3036 KB Output is correct
11 Correct 275 ms 16460 KB Output is correct
12 Correct 122 ms 31992 KB Output is correct
13 Correct 145 ms 42352 KB Output is correct
14 Correct 122 ms 29588 KB Output is correct
15 Correct 114 ms 19380 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 237 ms 6364 KB Output is correct
7 Correct 300 ms 5828 KB Output is correct
8 Correct 227 ms 5876 KB Output is correct
9 Correct 133 ms 6212 KB Output is correct
10 Correct 175 ms 3036 KB Output is correct
11 Correct 275 ms 16460 KB Output is correct
12 Correct 122 ms 31992 KB Output is correct
13 Correct 145 ms 42352 KB Output is correct
14 Correct 122 ms 29588 KB Output is correct
15 Correct 114 ms 19380 KB Output is correct
16 Execution timed out 3076 ms 40480 KB Time limit exceeded
17 Halted 0 ms 0 KB -