Submission #986770

#	Time	Username	Problem	Language	Result	Execution time	Memory
986770		MercubytheFirst	Election (BOI18_election)	C++17	0 / 100	5 ms	8280 KiB

election

#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define CDIV(a,b) (((a)+(b)-(1))/(b))
using ll = long long;
using ld = long double;
const ll inf = 1e9 + 37;
const ll mod = 1e9 + 7;
const ll N = 5e5 + 37;
const ld eps = 1e-9;
const ld PI = acos((ld)-1);
 

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v);
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


struct SegmentTree
{
  int t[2 * N] = {};
  int n = -37;
  SegmentTree(int sz) : n(sz) {
  }
  void update(int idx, int val) {
    for(t[idx += n] = val; idx > 1; idx >>= 1) {
      t[idx >> 1] = max(t[idx], t[idx ^ 1]);
    }
  }
  int query(int l, int r) {
    int ans = -inf;
    for(l += n, r += n; l <= r; l >>= 1, r >>= 1) {
      if(l & 1) {
        ans = max(ans, t[l++]);
      }
      if(!(r & 1)) {
        ans = max(ans, t[r--]);
      }
    }
    return ans;
  }
};

inline void solve(){
  int n;
  string s;
  cin >> n >> s;
  vector<int> norm(n + 1), rev(n + 1);
  SegmentTree normal_tree(n), rev_tree(n);
  for(int i = 0; i < n; ++i) {
    norm[i + 1] = norm[i] + (s[i] == 'C' ? -1 : +1);
    normal_tree.update(i + 1, norm[i + 1]);
  }
  reverse(s.begin(), s.end());
  for(int i = 0; i < n; ++i) {
    rev[i + 1] = rev[i] + (s[i] == 'C' ? -1 : +1);
    rev_tree.update(i + 1, rev[i + 1]);
  }
  // cout << norm << endl << rev << endl;
  int Q; 
  cin >> Q;
  while(Q--) {
    int l, r;
    cin >> l >> r;
    int nans = normal_tree.query(l, r) - norm[l - 1];
    int rans = rev_tree.query(n - r + 1, n - l + 1) - rev[n - r];
    cout << max({0, nans, rans}) << endl;
  }
}


 
signed main(){
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(NULL); 
  // signed t; cin >> t; while(t--)
    solve();
}

template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
  for(T& x : v)
    is >> x;
  return is;
}

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18