oj.uz

답안 #611866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
611866 2022-07-29T08:12:09 Z amunduzbaev Election (BOI18_election) C++17
82 / 100
 3000 ms 45352 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 = 250;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 3 ms 724 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 233 ms 6588 KB Output is correct
7 Correct 308 ms 5848 KB Output is correct
8 Correct 220 ms 5776 KB Output is correct
9 Correct 119 ms 6324 KB Output is correct
10 Correct 198 ms 2992 KB Output is correct
11 Correct 273 ms 17448 KB Output is correct
12 Correct 122 ms 34052 KB Output is correct
13 Correct 133 ms 45352 KB Output is correct
14 Correct 122 ms 31520 KB Output is correct
15 Correct 115 ms 20392 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 233 ms 6588 KB Output is correct
7 Correct 308 ms 5848 KB Output is correct
8 Correct 220 ms 5776 KB Output is correct
9 Correct 119 ms 6324 KB Output is correct
10 Correct 198 ms 2992 KB Output is correct
11 Correct 273 ms 17448 KB Output is correct
12 Correct 122 ms 34052 KB Output is correct
13 Correct 133 ms 45352 KB Output is correct
14 Correct 122 ms 31520 KB Output is correct
15 Correct 115 ms 20392 KB Output is correct
16 Execution timed out 3080 ms 41840 KB Time limit exceeded
17 Halted 0 ms 0 KB -