oj.uz

Submission #536242

# Submission time Handle Problem Language Result Execution time Memory
536242 2022-03-12T16:28:56 Z LamoreauxAJ Election (BOI18_election) C++14
100 / 100
 283 ms 27244 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 404 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 404 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 33 ms 3828 KB Output is correct
7 Correct 32 ms 3836 KB Output is correct
8 Correct 34 ms 3736 KB Output is correct
9 Correct 26 ms 3892 KB Output is correct
10 Correct 30 ms 3760 KB Output is correct
11 Correct 29 ms 3888 KB Output is correct
12 Correct 29 ms 3916 KB Output is correct
13 Correct 30 ms 3980 KB Output is correct
14 Correct 41 ms 3836 KB Output is correct
15 Correct 45 ms 3812 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 404 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 33 ms 3828 KB Output is correct
7 Correct 32 ms 3836 KB Output is correct
8 Correct 34 ms 3736 KB Output is correct
9 Correct 26 ms 3892 KB Output is correct
10 Correct 30 ms 3760 KB Output is correct
11 Correct 29 ms 3888 KB Output is correct
12 Correct 29 ms 3916 KB Output is correct
13 Correct 30 ms 3980 KB Output is correct
14 Correct 41 ms 3836 KB Output is correct
15 Correct 45 ms 3812 KB Output is correct
16 Correct 262 ms 26244 KB Output is correct
17 Correct 245 ms 25704 KB Output is correct
18 Correct 254 ms 26156 KB Output is correct
19 Correct 229 ms 25520 KB Output is correct
20 Correct 274 ms 25276 KB Output is correct
21 Correct 276 ms 27124 KB Output is correct
22 Correct 271 ms 26972 KB Output is correct
23 Correct 261 ms 27244 KB Output is correct
24 Correct 259 ms 26880 KB Output is correct
25 Correct 283 ms 26340 KB Output is correct