oj.uz

Submission #649256

# Submission time Handle Problem Language Result Execution time Memory
649256 2022-10-09T21:23:37 Z tvladm2009 Election (BOI18_election) C++14
100 / 100
 496 ms 41840 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 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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 464 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 49 ms 6344 KB Output is correct
7 Correct 47 ms 6292 KB Output is correct
8 Correct 48 ms 6188 KB Output is correct
9 Correct 42 ms 6284 KB Output is correct
10 Correct 49 ms 6216 KB Output is correct
11 Correct 50 ms 6348 KB Output is correct
12 Correct 50 ms 6368 KB Output is correct
13 Correct 49 ms 6428 KB Output is correct
14 Correct 51 ms 6380 KB Output is correct
15 Correct 50 ms 6300 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 49 ms 6344 KB Output is correct
7 Correct 47 ms 6292 KB Output is correct
8 Correct 48 ms 6188 KB Output is correct
9 Correct 42 ms 6284 KB Output is correct
10 Correct 49 ms 6216 KB Output is correct
11 Correct 50 ms 6348 KB Output is correct
12 Correct 50 ms 6368 KB Output is correct
13 Correct 49 ms 6428 KB Output is correct
14 Correct 51 ms 6380 KB Output is correct
15 Correct 50 ms 6300 KB Output is correct
16 Correct 496 ms 40788 KB Output is correct
17 Correct 418 ms 40772 KB Output is correct
18 Correct 432 ms 40944 KB Output is correct
19 Correct 373 ms 40328 KB Output is correct
20 Correct 460 ms 39904 KB Output is correct
21 Correct 475 ms 41568 KB Output is correct
22 Correct 482 ms 41568 KB Output is correct
23 Correct 487 ms 41840 KB Output is correct
24 Correct 459 ms 41416 KB Output is correct
25 Correct 469 ms 40940 KB Output is correct