oj.uz

Submission #60924

# Submission time Handle Problem Language Result Execution time Memory
60924 2018-07-25T01:57:15 Z ksun48 Election (BOI18_election) C++14
28 / 100
 3000 ms 32820 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

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

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 range_max(int a, int b){
	int z = psums[a];
	for(int j = a; j <= b; j++){
		z = max(z, psums[j]);
	}
	return z;
}

int range_min(int a, int b){
	int z = psums[a];
	for(int j = a; j <= b; j++){
		z = min(z, psums[j]);
	}
	return z;
}

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 z = 0;
	for(int i = a; i <= b; i++){
		for(int j = i; j <= b; j++){
			z = max(psums[j] - psums[i], z);
		}
	}
	return z;
}
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);
		}
	}
	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 'int main()':
election.cpp:71: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 13 ms 1016 KB Output is correct
2 Correct 15 ms 1252 KB Output is correct
3 Correct 15 ms 1348 KB Output is correct
4 Correct 15 ms 1348 KB Output is correct
5 Correct 14 ms 1348 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1016 KB Output is correct
2 Correct 15 ms 1252 KB Output is correct
3 Correct 15 ms 1348 KB Output is correct
4 Correct 15 ms 1348 KB Output is correct
5 Correct 14 ms 1348 KB Output is correct
6 Execution timed out 3012 ms 32820 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1016 KB Output is correct
2 Correct 15 ms 1252 KB Output is correct
3 Correct 15 ms 1348 KB Output is correct
4 Correct 15 ms 1348 KB Output is correct
5 Correct 14 ms 1348 KB Output is correct
6 Execution timed out 3012 ms 32820 KB Time limit exceeded
7 Halted 0 ms 0 KB -