제출 #1365355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365355		TraianDanciu	Election (BOI18_election)	C++20	100 / 100	269 ms	20356 KiB

election

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 500000;

string s;

struct SegmentTree {
  struct Node {
    int pref, suff, sum, answer;
  } tree[4 * MAXN];
  int n;

  Node join(Node a, Node b) {
    return Node {
      max(a.pref, a.sum + b.pref),
      max(a.suff + b.sum, b.suff),
      a.sum + b.sum,
      max({a.answer + b.sum, a.sum + b.answer, a.pref + b.suff})
    };
  }

  void build(int node, int left, int right) {
    if(left == right) {
      if(s[left] == 'C') {
        tree[node] = {0, 0, -1, 0};
      } else {
        tree[node] = {1, 1, 1, 1};
      }
    } else {
      int middle = (left + right) / 2;
      build(2 * node, left, middle);
      build(2 * node + 1, middle + 1, right);
      tree[node] = join(tree[2 * node], tree[2 * node + 1]);
    }
  }

  void init(int n) {
    this->n = n;
    build(1, 1, n);
  }

  Node query(int node, int left, int right, int qleft, int qright) {
    if(qleft <= left && right <= qright) {
      return tree[node];
    }
    int middle = (left + right) / 2;
    Node answer = {0, 0, 0, 0};
    if(qleft <= middle) {
      answer = join(answer, query(2 * node, left, middle, qleft, qright));
    }
    if(middle < qright) {
      answer = join(answer, query(2 * node + 1, middle + 1, right, qleft, qright));
    }
    return answer;
  }

  int query(int st, int dr) {
    return query(1, 1, n, st, dr).answer;
  }
} aint;

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

  int n;
  cin >> n >> s;
  s = "#" + s;
  aint.init(n);
  int q;
  cin >> q;
  while(q--) {
    int st, dr;
    cin >> st >> dr;
    cout << aint.query(st, dr) << "\n";
  }
  return 0;
}

• 서브태스크 1: 28 / 28
• 서브태스크 2: 54 / 54
• 서브태스크 3: 18 / 18