oj.uz

Submission #611857

# Submission time Handle Problem Language Result Execution time Memory
611857 2022-07-29T08:09:49 Z amunduzbaev Election (BOI18_election) C++17
82 / 100
 3000 ms 96892 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 = 600;
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 6 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 7 ms 1476 KB Output is correct
5 Correct 3 ms 980 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 7 ms 1476 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 432 ms 8212 KB Output is correct
7 Correct 390 ms 7608 KB Output is correct
8 Correct 361 ms 6680 KB Output is correct
9 Correct 206 ms 7476 KB Output is correct
10 Correct 358 ms 2676 KB Output is correct
11 Correct 518 ms 36088 KB Output is correct
12 Correct 202 ms 70140 KB Output is correct
13 Correct 272 ms 96892 KB Output is correct
14 Correct 224 ms 66364 KB Output is correct
15 Correct 173 ms 39888 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 7 ms 1476 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 432 ms 8212 KB Output is correct
7 Correct 390 ms 7608 KB Output is correct
8 Correct 361 ms 6680 KB Output is correct
9 Correct 206 ms 7476 KB Output is correct
10 Correct 358 ms 2676 KB Output is correct
11 Correct 518 ms 36088 KB Output is correct
12 Correct 202 ms 70140 KB Output is correct
13 Correct 272 ms 96892 KB Output is correct
14 Correct 224 ms 66364 KB Output is correct
15 Correct 173 ms 39888 KB Output is correct
16 Execution timed out 3077 ms 52360 KB Time limit exceeded
17 Halted 0 ms 0 KB -