oj.uz

Submission #61077

# Submission time Handle Problem Language Result Execution time Memory
61077 2018-07-25T07:42:39 Z ksun48 Election (BOI18_election) C++14
Compilation error
 0 ms 0 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<<15+b) == memo.end()){
		memo[a<<15+b] = max_psum(a, b, l, r);
	}
	return memo[a<<15+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 get(int, int, int, int)':
election.cpp:51:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  if(memo.find(a<<15+b) == memo.end()){
                  ~~^~
election.cpp:51:22: error: no matching function for call to 'std::map<std::pair<int, int>, int>::find(int)'
  if(memo.find(a<<15+b) == memo.end()){
                      ^
In file included from /usr/include/c++/7/map:61:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from election.cpp:1:
/usr/include/c++/7/bits/stl_map.h:1163:7: note: candidate: std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
       find(const key_type& __x)
       ^~~~
/usr/include/c++/7/bits/stl_map.h:1163:7: note:   no known conversion for argument 1 from 'int' to 'const key_type& {aka const std::pair<int, int>&}'
/usr/include/c++/7/bits/stl_map.h:1169:2: note: candidate: template<class _Kt> decltype (((std::map<_Key, _Tp, _Compare, _Alloc>*)this)->std::map<_Key, _Tp, _Compare, _Alloc>::_M_t._M_find_tr(__x)) std::map<_Key, _Tp, _Compare, _Alloc>::find(const _Kt&) [with _Kt = _Kt; _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]
  find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
  ^~~~
/usr/include/c++/7/bits/stl_map.h:1169:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_map.h: In substitution of 'template<class _Kt> decltype (((std::map<std::pair<int, int>, int>*)this)->std::map<std::pair<int, int>, int>::_M_t.std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::_M_find_tr(__x)) std::map<std::pair<int, int>, int>::find<_Kt>(const _Kt&) [with _Kt = int]':
election.cpp:51:22:   required from here
/usr/include/c++/7/bits/stl_map.h:1169:2: error: no matching function for call to 'std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::_M_find_tr(const int&)'
In file included from /usr/include/c++/7/map:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from election.cpp:1:
/usr/include/c++/7/bits/stl_tree.h:1212:2: note: candidate: template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_find_tr(const _Kt&) [with _Kt = _Kt; _Req = _Req; _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]
  _M_find_tr(const _Kt& __k)
  ^~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1212:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_tree.h:1209:9: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<std::pair<int, int> >, int, void>'
         typename _Req =
         ^~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1222:2: note: candidate: template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_find_tr(const _Kt&) const [with _Kt = _Kt; _Req = _Req; _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]
  _M_find_tr(const _Kt& __k) const
  ^~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1222:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_tree.h:1219:9: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<std::pair<int, int> >, int, void>'
         typename _Req =
         ^~~~~~~~
In file included from /usr/include/c++/7/map:61:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from election.cpp:1:
/usr/include/c++/7/bits/stl_map.h:1188:7: note: candidate: std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const key_type&) const [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
       find(const key_type& __x) const
       ^~~~
/usr/include/c++/7/bits/stl_map.h:1188:7: note:   no known conversion for argument 1 from 'int' to 'const key_type& {aka const std::pair<int, int>&}'
/usr/include/c++/7/bits/stl_map.h:1194:2: note: candidate: template<class _Kt> decltype (((const std::map<_Key, _Tp, _Compare, _Alloc>*)this)->std::map<_Key, _Tp, _Compare, _Alloc>::_M_t._M_find_tr(__x)) std::map<_Key, _Tp, _Compare, _Alloc>::find(const _Kt&) const [with _Kt = _Kt; _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]
  find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
  ^~~~
/usr/include/c++/7/bits/stl_map.h:1194:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_map.h: In substitution of 'template<class _Kt> decltype (((const std::map<std::pair<int, int>, int>*)this)->std::map<std::pair<int, int>, int>::_M_t.std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::_M_find_tr(__x)) std::map<std::pair<int, int>, int>::find<_Kt>(const _Kt&) const [with _Kt = int]':
election.cpp:51:22:   required from here
/usr/include/c++/7/bits/stl_map.h:1194:2: error: no matching function for call to 'std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::_M_find_tr(const int&) const'
In file included from /usr/include/c++/7/map:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from election.cpp:1:
/usr/include/c++/7/bits/stl_tree.h:1212:2: note: candidate: template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_find_tr(const _Kt&) [with _Kt = _Kt; _Req = _Req; _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]
  _M_find_tr(const _Kt& __k)
  ^~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1212:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_tree.h:1209:9: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<std::pair<int, int> >, int, void>'
         typename _Req =
         ^~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1222:2: note: candidate: template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_find_tr(const _Kt&) const [with _Kt = _Kt; _Req = _Req; _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]
  _M_find_tr(const _Kt& __k) const
  ^~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1222:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_tree.h:1219:9: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<std::pair<int, int> >, int, void>'
         typename _Req =
         ^~~~~~~~
election.cpp:52:13: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   memo[a<<15+b] = max_psum(a, b, l, r);
           ~~^~
election.cpp:52:7: error: no match for 'operator[]' (operand types are 'std::map<std::pair<int, int>, int>' and 'int')
   memo[a<<15+b] = max_psum(a, b, l, r);
       ^
In file included from /usr/include/c++/7/map:61:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from election.cpp:1:
/usr/include/c++/7/bits/stl_map.h:484:7: note: candidate: std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
       operator[](const key_type& __k)
       ^~~~~~~~
/usr/include/c++/7/bits/stl_map.h:484:7: note:   no known conversion for argument 1 from 'int' to 'const key_type& {aka const std::pair<int, int>&}'
/usr/include/c++/7/bits/stl_map.h:504:7: note: candidate: std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
       operator[](key_type&& __k)
       ^~~~~~~~
/usr/include/c++/7/bits/stl_map.h:504:7: note:   no known conversion for argument 1 from 'int' to 'std::map<std::pair<int, int>, int>::key_type&& {aka std::pair<int, int>&&}'
election.cpp:54:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  return memo[a<<15+b];
                 ~~^~
election.cpp:54:13: error: no match for 'operator[]' (operand types are 'std::map<std::pair<int, int>, int>' and 'int')
  return memo[a<<15+b];
             ^
In file included from /usr/include/c++/7/map:61:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from election.cpp:1:
/usr/include/c++/7/bits/stl_map.h:484:7: note: candidate: std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
       operator[](const key_type& __k)
       ^~~~~~~~
/usr/include/c++/7/bits/stl_map.h:484:7: note:   no known conversion for argument 1 from 'int' to 'const key_type& {aka const std::pair<int, int>&}'
/usr/include/c++/7/bits/stl_map.h:504:7: note: candidate: std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
       operator[](key_type&& __k)
       ^~~~~~~~
/usr/include/c++/7/bits/stl_map.h:504:7: note:   no known conversion for argument 1 from 'int' to 'std::map<std::pair<int, int>, int>::key_type&& {aka std::pair<int, int>&&}'
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++){
                 ~~^~~~~~~~~~