oj.uz

Submission #61071

# Submission time Handle Problem Language Result Execution time Memory
61071 2018-07-25T07:37:16 Z ksun48 Election (BOI18_election) C++14
82 / 100
 3000 ms 202148 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(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:82: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 14 ms 1400 KB Output is correct
2 Correct 13 ms 1452 KB Output is correct
3 Correct 15 ms 1452 KB Output is correct
4 Correct 15 ms 1472 KB Output is correct
5 Correct 16 ms 1648 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1400 KB Output is correct
2 Correct 13 ms 1452 KB Output is correct
3 Correct 15 ms 1452 KB Output is correct
4 Correct 15 ms 1472 KB Output is correct
5 Correct 16 ms 1648 KB Output is correct
6 Correct 1480 ms 50328 KB Output is correct
7 Correct 486 ms 50328 KB Output is correct
8 Correct 860 ms 50328 KB Output is correct
9 Correct 997 ms 50328 KB Output is correct
10 Correct 1392 ms 50328 KB Output is correct
11 Correct 1552 ms 50376 KB Output is correct
12 Correct 1394 ms 50376 KB Output is correct
13 Correct 1637 ms 50376 KB Output is correct
14 Correct 1642 ms 50400 KB Output is correct
15 Correct 1412 ms 50400 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1400 KB Output is correct
2 Correct 13 ms 1452 KB Output is correct
3 Correct 15 ms 1452 KB Output is correct
4 Correct 15 ms 1472 KB Output is correct
5 Correct 16 ms 1648 KB Output is correct
6 Correct 1480 ms 50328 KB Output is correct
7 Correct 486 ms 50328 KB Output is correct
8 Correct 860 ms 50328 KB Output is correct
9 Correct 997 ms 50328 KB Output is correct
10 Correct 1392 ms 50328 KB Output is correct
11 Correct 1552 ms 50376 KB Output is correct
12 Correct 1394 ms 50376 KB Output is correct
13 Correct 1637 ms 50376 KB Output is correct
14 Correct 1642 ms 50400 KB Output is correct
15 Correct 1412 ms 50400 KB Output is correct
16 Execution timed out 3059 ms 202148 KB Time limit exceeded
17 Halted 0 ms 0 KB -