oj.uz

Submission #61074

# Submission time Handle Problem Language Result Execution time Memory
61074 2018-07-25T07:39:18 Z ksun48 Election (BOI18_election) C++14
82 / 100
 3000 ms 144784 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

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

const int MAXJ = 20;
vector<int> jumpmin[MAXJ];
vector<int> jumpmax[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))]);
			}
		}
	}
}

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)]);
}

map<pair<int,int>, int> memo;

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

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

int max_psum(int a, int b, int l, int r){
	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);
	}
	if(m <= a){
		return max_psum(a, b, m, r);
	}
	int ans = 0;
	ans = max(ans, get(a, m, l, m));
	ans = max(ans, get(m, b, m, r));
	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);
}
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

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

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1016 KB Output is correct
2 Correct 9 ms 1016 KB Output is correct
3 Correct 10 ms 1016 KB Output is correct
4 Correct 11 ms 1016 KB Output is correct
5 Correct 10 ms 1160 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1016 KB Output is correct
2 Correct 9 ms 1016 KB Output is correct
3 Correct 10 ms 1016 KB Output is correct
4 Correct 11 ms 1016 KB Output is correct
5 Correct 10 ms 1160 KB Output is correct
6 Correct 838 ms 21004 KB Output is correct
7 Correct 612 ms 21244 KB Output is correct
8 Correct 710 ms 21244 KB Output is correct
9 Correct 572 ms 21244 KB Output is correct
10 Correct 772 ms 21244 KB Output is correct
11 Correct 698 ms 21244 KB Output is correct
12 Correct 717 ms 21456 KB Output is correct
13 Correct 715 ms 21456 KB Output is correct
14 Correct 818 ms 21456 KB Output is correct
15 Correct 807 ms 21456 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1016 KB Output is correct
2 Correct 9 ms 1016 KB Output is correct
3 Correct 10 ms 1016 KB Output is correct
4 Correct 11 ms 1016 KB Output is correct
5 Correct 10 ms 1160 KB Output is correct
6 Correct 838 ms 21004 KB Output is correct
7 Correct 612 ms 21244 KB Output is correct
8 Correct 710 ms 21244 KB Output is correct
9 Correct 572 ms 21244 KB Output is correct
10 Correct 772 ms 21244 KB Output is correct
11 Correct 698 ms 21244 KB Output is correct
12 Correct 717 ms 21456 KB Output is correct
13 Correct 715 ms 21456 KB Output is correct
14 Correct 818 ms 21456 KB Output is correct
15 Correct 807 ms 21456 KB Output is correct
16 Execution timed out 3052 ms 144784 KB Time limit exceeded
17 Halted 0 ms 0 KB -