oj.uz

Submission #649254

# Submission time Handle Problem Language Result Execution time Memory
649254 2022-10-09T21:21:42 Z tvladm2009 Election (BOI18_election) C++14
0 / 100
 2 ms 468 KB 
#include <bits/stdc++.h>

using ll = long long;

int const nmax = 500000;

int a[1 + nmax];

class SegmentTree {
  private:
    struct Node {
      int sum;
      int minsuff;
      int maxpref;
      int uphill;
    };
    std::vector<Node> aint;
  public:
    SegmentTree(int n) {
      aint.resize(4 * n + 1);
    }

    Node join(Node lson, Node rson) {
      Node ans;
      ans.sum = lson.sum + rson.sum;
      ans.minsuff = std::min(rson.minsuff, rson.sum + lson.minsuff);
      ans.maxpref = std::max(lson.maxpref, lson.sum + rson.maxpref);
      ans.uphill = std::max({lson.maxpref + rson.minsuff, lson.sum + rson.uphill, lson.uphill + rson.sum});
      return ans;
    }

    void build(int v, int from, int to) {
      if(from == to)
        aint[v] = Node{a[from], std::max(0, a[from]), std::max(0, a[from]), std::max(0, a[from])};
      else {
        int mid = (from + to) / 2;
        build(2 * v, from, mid);
        build(2 * v + 1, mid + 1, to);
        aint[v] = join(aint[2 * v], aint[2 * v + 1]);
      }
    }

    Node query(int v, int from, int to, int l, int r) {
      if(l > r)
        return Node{0, 0, 0, 0};
      else if(l <= from && to <= r)
        return aint[v];
      else {
        int mid = (from + to) / 2;
        return join(query(2 * v, from, mid, l, std::min(mid, r)), query(2 * v + 1, mid + 1, to, std::max(l, mid + 1), r));
      }
    }
};

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::string s;
  std::cin >> n >> s;
  for(int i = 1;i <= n; i++) {
    if(s[i - 1] == 'C')
      a[i] = -1;
    else
      a[i] = 1;
  }
  SegmentTree aint(n);
  aint.build(1, 1, n);

  int q;
  std::cin >> q;
  for(int i = 1;i <= q; i++) {
    int l, r;
    std::cin >> l >> r;
    std::cout << aint.query(1, 1, n, l, r).uphill << "\n";
  }
  return 0;
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -