oj.uz

Submission #611864

# Submission time Handle Problem Language Result Execution time Memory
611864 2022-07-29T08:11:43 Z amunduzbaev Election (BOI18_election) C++17
82 / 100
 3000 ms 54192 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 = 300;
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 5 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 2 ms 724 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 244 ms 6668 KB Output is correct
7 Correct 388 ms 6184 KB Output is correct
8 Correct 241 ms 5980 KB Output is correct
9 Correct 180 ms 6404 KB Output is correct
10 Correct 226 ms 2960 KB Output is correct
11 Correct 319 ms 19996 KB Output is correct
12 Correct 132 ms 39284 KB Output is correct
13 Correct 146 ms 54192 KB Output is correct
14 Correct 134 ms 36444 KB Output is correct
15 Correct 125 ms 23764 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 244 ms 6668 KB Output is correct
7 Correct 388 ms 6184 KB Output is correct
8 Correct 241 ms 5980 KB Output is correct
9 Correct 180 ms 6404 KB Output is correct
10 Correct 226 ms 2960 KB Output is correct
11 Correct 319 ms 19996 KB Output is correct
12 Correct 132 ms 39284 KB Output is correct
13 Correct 146 ms 54192 KB Output is correct
14 Correct 134 ms 36444 KB Output is correct
15 Correct 125 ms 23764 KB Output is correct
16 Execution timed out 3058 ms 43328 KB Time limit exceeded
17 Halted 0 ms 0 KB -