oj.uz

Submission #61001

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

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

struct node{
	node *l, *r;
	int lx, rx;
	int maxv, minv;
};
node * build(int lx, int rx){
	node * v = new node();
	v->lx = lx;
	v->rx = rx;
	if(lx == rx){
		v->l = v->r = NULL;
		v->maxv = v->minv = psums[lx];
	} else {
		int mx = (lx + rx) / 2;
		v->l = build(lx, mx);
		v->r = build(mx + 1, rx);
		v->maxv = max(v->l->maxv, v->r->maxv);
		v->minv = min(v->l->minv, v->r->minv);
	}
	return v;
}


node * tree;

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

const int INF = 1000000000;
int range_max(node * v, int a, int b){
	if(b < v->lx || v->rx < a) return -INF;
	if(a <= v->lx && v->rx <= b) return v->maxv;
	return max(range_max(v->l, a, b), range_max(v->r, a, b));
}
int range_min(node * v, int a, int b){
	if(b < v->lx || v->rx < a) return INF;
	if(a <= v->lx && v->rx <= b) return v->minv;
	return min(range_min(v->l, a, b), range_min(v->r, 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(tree, m, b) - range_min(tree, 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);
		}
	}

	tree = build(0, n);

	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:92: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 20 ms 1272 KB Output is correct
2 Correct 23 ms 1272 KB Output is correct
3 Correct 21 ms 1420 KB Output is correct
4 Correct 18 ms 1420 KB Output is correct
5 Correct 18 ms 1420 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1272 KB Output is correct
2 Correct 23 ms 1272 KB Output is correct
3 Correct 21 ms 1420 KB Output is correct
4 Correct 18 ms 1420 KB Output is correct
5 Correct 18 ms 1420 KB Output is correct
6 Correct 1774 ms 45976 KB Output is correct
7 Correct 540 ms 45976 KB Output is correct
8 Correct 1075 ms 45976 KB Output is correct
9 Correct 1448 ms 45976 KB Output is correct
10 Correct 2117 ms 45976 KB Output is correct
11 Correct 2166 ms 45976 KB Output is correct
12 Correct 1904 ms 45976 KB Output is correct
13 Correct 2076 ms 45976 KB Output is correct
14 Correct 2186 ms 46060 KB Output is correct
15 Correct 2086 ms 46060 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1272 KB Output is correct
2 Correct 23 ms 1272 KB Output is correct
3 Correct 21 ms 1420 KB Output is correct
4 Correct 18 ms 1420 KB Output is correct
5 Correct 18 ms 1420 KB Output is correct
6 Correct 1774 ms 45976 KB Output is correct
7 Correct 540 ms 45976 KB Output is correct
8 Correct 1075 ms 45976 KB Output is correct
9 Correct 1448 ms 45976 KB Output is correct
10 Correct 2117 ms 45976 KB Output is correct
11 Correct 2166 ms 45976 KB Output is correct
12 Correct 1904 ms 45976 KB Output is correct
13 Correct 2076 ms 45976 KB Output is correct
14 Correct 2186 ms 46060 KB Output is correct
15 Correct 2086 ms 46060 KB Output is correct
16 Execution timed out 3026 ms 147972 KB Time limit exceeded
17 Halted 0 ms 0 KB -