Submission #536235

#	Time	Username	Problem	Language	Result	Execution time	Memory
536235		LamoreauxAJ	Election (BOI18_election)	C++14	0 / 100	1 ms	340 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;
  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;
    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});
    else st.set(i, Node{-1, -1, -1});
  }
  st.build();
  while (Q--) {
    int l, r; cin >> l >> r;
    auto res = st.query(l - 1, r - 1);
    cout << -min(res.mnl, res.mnr) << "\n";
  }
}

Compilation message (stderr)

election.cpp: In function 'void solve()':
election.cpp:58:15: warning: 'res[1].Node::s' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     r.s = a.s + b.s;
      |           ~~~~^~~~~
election.cpp:25:7: note: 'res[1].Node::s' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:25:7: warning: 'res[1].Node::mnr' may be used uninitialized in this function [-Wmaybe-uninitialized]
election.cpp:56:28: warning: 'res[1].Node::mnl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |     r.mnl = min(a.mnl, a.s + b.mnl);
      |                        ~~~~^~~~~~~
election.cpp:25:7: note: 'res[1].Node::mnl' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:58:15: warning: 'res[0].Node::s' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     r.s = a.s + b.s;
      |           ~~~~^~~~~
election.cpp:25:7: note: 'res[0].Node::s' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:57:28: warning: 'res[0].Node::mnr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     r.mnr = min(b.mnr, b.s + a.mnr);
      |                        ~~~~^~~~~~~
election.cpp:25:7: note: 'res[0].Node::mnr' was declared here
   25 |     T res[2];
      |       ^~~
election.cpp:25:7: warning: 'res[0].Node::mnl' may be used uninitialized in this function [-Wmaybe-uninitialized]

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