Submission #649256

#	Time	Username	Problem	Language	Result	Execution time	Memory
649256		tvladm2009	Election (BOI18_election)	C++14	100 / 100	496 ms	41840 KiB

election

#include <bits/stdc++.h>

using ll = long long;

int const nmax = 500000;

int a[1 + nmax];

class SegmentTree {
  private:
    struct Node {
      int sum;
      int maxsuff;
      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.maxsuff = std::max(rson.maxsuff, rson.sum + lson.maxsuff);
      ans.maxpref = std::max(lson.maxpref, lson.sum + rson.maxpref);
      ans.uphill = std::max({lson.maxpref + rson.maxsuff, 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: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18