Submission #536242

#	Time	Username	Problem	Language	Result	Execution time	Memory
536242		LamoreauxAJ	Election (BOI18_election)	C++14	100 / 100	283 ms	27244 KiB

election

#include <bits/stdc++.h>


using namespace std;  
 

// cp-end


// cp-begin: segment-tree snippet
template <typename T, T (*Op)(T, T)> struct SegmentTree {
  int N;
  vector<T> t;
  SegmentTree() {}
  SegmentTree(int N) : N(N), t(2 * N) {};
  
  void set(int p, T v) { t[p + N] = v; }
  void build() {
    for (int i = N - 1; i > 0; i--)
      t[i] = Op(t[i << 1], t[i << 1 | 1]);
  }
  
  T query(int l, int r) {
    r++;
    T res[2];
    bool set[2] = {false};
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res[0] = set[0] ? Op(res[0], t[l++]) : (set[0] = true, t[l++]);
      if (r & 1) res[1] = set[1] ? Op(t[--r], res[1]) : (set[1] = true, t[--r]);
    }
    if (!set[0]) return res[1];
    else if (!set[1]) return res[0];
    else return Op(res[0], res[1]);
  }
  
};
// cp-end


// cp-end


void solve();

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(12);
  solve(); return 0;
}


struct Node {
  int mnl, mnr, s, ans;
  static Node op(Node a, Node b) {
    Node r;
    r.mnl = min(a.mnl, a.s + b.mnl);
    r.mnr = min(b.mnr, b.s + a.mnr);
    r.s = a.s + b.s;
    r.ans = max(-a.mnl-b.mnr, max(-a.s + b.ans, -b.s + a.ans));
    return r;
  }
};

int N, Q;
string S;
SegmentTree<Node, Node::op> st;

void solve() {
  cin >> N >> S >> Q;
  st = SegmentTree<Node, Node::op>(N);
  for (int i = 0; i < N; i++) {
    if (S[i] == 'C') st.set(i, Node{0, 0, 1, 0});
    else st.set(i, Node{-1, -1, -1, 1});
  }
  st.build();
  while (Q--) {
    int l, r; cin >> l >> r;
    auto res = st.query(l - 1, r - 1);
    cout << res.ans << "\n";
  }
}

Compilation message (stderr)

election.cpp: In function 'void solve()':
election.cpp:59:40: warning: 'res[1].Node::ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     r.ans = max(-a.mnl-b.mnr, max(-a.s + b.ans, -b.s + a.ans));
      |                                   ~~~~~^~~~~~~
election.cpp:25:7: note: 'res[1].Node::ans' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:59:54: warning: 'res[1].Node::s' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     r.ans = max(-a.mnl-b.mnr, max(-a.s + b.ans, -b.s + a.ans));
      |                                                 ~~~~~^~~~~~~
election.cpp:25:7: note: 'res[1].Node::s' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:59:23: warning: 'res[1].Node::mnr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     r.ans = max(-a.mnl-b.mnr, max(-a.s + b.ans, -b.s + a.ans));
      |                 ~~~~~~^~~~~~
election.cpp:25:7: note: 'res[1].Node::mnr' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:59:54: warning: 'res[0].Node::ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     r.ans = max(-a.mnl-b.mnr, max(-a.s + b.ans, -b.s + a.ans));
      |                                                 ~~~~~^~~~~~~
election.cpp:25:7: note: 'res[0].Node::ans' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:59:40: warning: 'res[0].Node::s' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     r.ans = max(-a.mnl-b.mnr, max(-a.s + b.ans, -b.s + a.ans));
      |                                   ~~~~~^~~~~~~
election.cpp:25:7: note: 'res[0].Node::s' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:59:17: warning: 'res[0].Node::mnl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     r.ans = max(-a.mnl-b.mnr, max(-a.s + b.ans, -b.s + a.ans));
      |                 ^~~~~~
election.cpp:25:7: note: 'res[0].Node::mnl' was declared here
   25 |     T res[2];
      |       ^~~

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