Submission #361606

#	Time	Username	Problem	Language	Result	Execution time	Memory
361606		anayk	Election (BOI18_election)	C++14	0 / 100	8 ms	512 KiB

election

#include <iostream>
#include <vector>

#define left (id+1)
#define mid ((l+r)/2)
#define right (id+2*(mid-l+1))

int k;

struct seg
{
  std::vector<std::pair<int, int> > arr;

  std::pair<int, int> merge(std::pair<int, int> l, std::pair<int, int> r) {
    int change = std::min(l.second, r.first);
    return {l.first + r.first - change, r.second + l.second - change};
  }

  void update(int x, std::pair<int, int> val, int id = 0, int l = 0, int r = k-1) {
    if(l == r) {
      arr[id] = val;
      return;
    }

    if(x <= mid)
      update(x, val, left, l, mid);
    else
      update(x, val, right, mid+1, r);

    arr[id] = merge(arr[left], arr[right]);
  }

  std::pair<int, int> query(int x, int y, int id = 0, int l = 0, int r = k-1) {
    if(y < l || r < x)
      return {0, 0};

    if(x <= l && r <= y)
      return arr[id];

    return merge(query(x, y, left, l, mid), query(x, y, right, mid+1, r));
  }
};

signed main() {
  std::cin >> k;

  std::string s;
  std::cin >> s;

  seg forw, back;
  forw.arr = back.arr = std::vector<std::pair<int, int> >(2*k-1, {0, 0});
  for(int i = 0; i < k; i++) {
    if(s[i] == 'C') {
      forw.update(i, {0, 1});
      back.update(i, {1, 0});
    }
    else {
      forw.update(i, {1, 0});
      back.update(i, {0, 1});
    }
  }

  int q;
  std::cin >> q;

  while(q--) {
    int l, r;
    std::cin >> l >> r;
    l--; r--;

    std::cout << std::max(forw.query(l, r).first, back.query(l, r).second) << std::endl;
  }

  return 0;
}

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