Submission #61084

#	Time	Username	Problem	Language	Result	Execution time	Memory
61084		ksun48	Election (BOI18_election)	C++14	100 / 100	2031 ms	123956 KiB

election

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int n;
int q;
string s;
vector<int> psums;

const int INF = 1000000000;
const int MAXJ = 20;
vector<int> jumpmin[MAXJ];
vector<int> jumpmax[MAXJ];

vector<int> memo[MAXJ];

void init(){
	for(int b = 0; b < MAXJ; b++){
		jumpmin[b].resize(psums.size());
		jumpmax[b].resize(psums.size());
		if(b == 0){
			for(int i = 0; i < psums.size(); i++){
				jumpmax[b][i] = psums[i];
				jumpmin[b][i] = psums[i];
			}
		} else {
			for(int i = 0; i + (1<<b) <= psums.size(); i++){
				jumpmax[b][i] = max(jumpmax[b-1][i], jumpmax[b-1][i + (1<<(b-1))]);
				jumpmin[b][i] = min(jumpmin[b-1][i], jumpmin[b-1][i + (1<<(b-1))]);
			}
		}
		memo[b].resize(psums.size());
		for(int i = 0; i < psums.size(); i++){
			memo[b][i] = INF;
		}
	}
}

int range_max(int a, int b){
	b++;
	int c = 31 - __builtin_clz(b-a);
	return max(jumpmax[c][a], jumpmax[c][b-(1<<c)]);
}

int range_min(int a, int b){
	b++;
	int c = 31 - __builtin_clz(b-a);
	return min(jumpmin[c][a], jumpmin[c][b-(1<<c)]);
}


// [a,b] in [l,r]

int max_psum(int a, int b, int l, int r, int lv);
int get(int a, int b, int l, int r, int lv){
	if(a != l || b != r) return max_psum(a, b, l, r, lv);
	if(memo[lv][a] == INF){
		memo[lv][a] = max_psum(a, b, l, r, lv);
	}
	return memo[lv][a];
}

int max_psum(int a, int b, int l, int r, int lv){
	if(a == b || b <= l || r <= a) return 0;
	int m = (l + r) / 2;
	if(m == l){
		return max(0, psums[b] - psums[a]);
	}
	if(b <= m){
		return max_psum(a, b, l, m, lv + 1);
	}
	if(m <= a){
		return max_psum(a, b, m, r, lv + 1);
	}
	int ans = 0;
	ans = max(ans, get(a, m, l, m, lv + 1));
	ans = max(ans, get(m, b, m, r, lv + 1));
	ans = max(ans, range_max(m, b) - range_min(a, m));
	return ans;
}

int max_psum_first(int a, int b){
	return max_psum(a, b, 0, n, 0);
}
int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> s >> q;
	psums.push_back(0);
	for(int i = 0; i < s.size(); i++){
		if(s[i] == 'C'){
			psums.push_back(psums[psums.size() - 1] + 1);
		} else {
			psums.push_back(psums[psums.size() - 1] - 1);
		}
	}
	init();

	for(int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		l--; r--;
		r++;
		int a = max_psum_first(l, r);
		cout << a - (psums[r] - psums[l]) << '\n';
	}
}

Compilation message (stderr)

election.cpp: In function 'void init()':
election.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < psums.size(); i++){
                   ~~^~~~~~~~~~~~~~
election.cpp:27:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i + (1<<b) <= psums.size(); i++){
                   ~~~~~~~~~~~^~~~~~~~~~~~~~~
election.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < psums.size(); i++){
                  ~~^~~~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++){
                 ~~^~~~~~~~~~

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18