Submission #46134235

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

template <typename Info>
struct SegmentTree {
  struct Node : public Info {
    int l, r, ts;
    Node *lch, *rch;
    Node(int l_ = 0, int r_ = 0, int ts_ = 0)
        : l(l_), r(r_), ts(ts_), lch(nullptr), rch(nullptr) {}
    Node(Node* x, int ts_ = 0) {
      *this = *x;
      this->ts = ts_;
    }
  };

  int l_range, r_range;
  Node* root;
  bool persist;
  int ts;
  SegmentTree(int l, int r, bool persist_ = false)
      : l_range(l), r_range(r), root(nullptr), persist(persist_), ts(0) {
    assert(l_range <= r_range);
  }

  void PushDown(Node* x) {
    if (x->NeedPushDown()) {
      if (persist) {
        if (x->lch && x->lch->ts != ts) x->lch = new Node(x->lch, ts);
        if (x->rch && x->rch->ts != ts) x->rch = new Node(x->rch, ts);
      }
      x->PushDown();
    }
  }

  template <typename F>
  Node* Modify(int from, int to, F f) {
    assert(l_range <= from && from <= to && to <= r_range);
    std::function<Node*(Node*, int, int)> Modify = [&](Node* x, int l, int r) {
      if (!x) {
        x = new Node(l, r, ts);
      } else if (persist && x->ts != ts) {
        x = new Node(x, ts);
      }
      if (from <= x->l && x->r <= to) {
        f(x);
        return x;
      }
      PushDown(x);
      int m = l + (r - l) / 2;
      if (from <= m) x->lch = Modify(x->lch, l, m);
      if (to > m) x->rch = Modify(x->rch, m + 1, r);
      x->Update();
      return x;
    };
    root = Modify(root, l_range, r_range);
    return root;
  }

  template <typename F>
  Node* ModifyPath(int p, F f) {
    assert(l_range <= p && p <= r_range);
    std::function<Node*(Node*, int, int)> Dfs = [&](Node* x, int l, int r) {
      if (!x) {
        x = new Node(l, r, ts);
      } else if (persist && x->ts != ts) {
        x = new Node(x, ts);
      }
      f(x);
      if (x->l == x->r) return x;
      PushDown(x);
      int m = l + (r - l) / 2;
      if (p <= m) x->lch = Dfs(x->lch, l, m);
      else x->rch = Dfs(x->rch, m + 1, r);
      x->Update();
      return x;
    };
    root = Dfs(root, l_range, r_range);
    return root;
  }

  std::vector<Node*> GetAllNodes(int from, int to) {
    assert(l_range <= from && from <= to && to <= r_range);
    std::vector<Node*> all;
    std::function<void(Node*, int, int, int, int)> Dfs =
        [&](Node* x, int l, int r, int from, int to) {
          if (!x) return;
          if (from <= l && r <= to) {
            all.push_back(x);
            return;
          }
          PushDown(x);
          int m = l + (r - l) / 2;
          if (from <= m) Dfs(x->lch, l, m, from, to);
          if (to > m) Dfs(x->rch, m + 1, r, from, to);
        };
    Dfs(root, l_range, r_range, from, to);
    return all;
  }

  template <typename F>
  int GetFirstAfter(int p, F f) {
    assert(l_range <= p && p <= r_range);
    auto nodes = GetAllNodes(p, r_range);
    for (auto x : nodes) {
      if (f(x)) {
        while (x->r > x->l) {
          assert(f(x));
          PushDown(x);
          if (x->lch && f(x->lch)) {
            x = x->lch;
          } else {
            x = x->rch;
          }
        }
        return x->l;
      }
    }
    return -1;
  }

  template <typename F>
  int GetLastBefore(int p, F f) {
    assert(l_range <= p && p <= r_range);
    auto nodes = GetAllNodes(l_range, p);
    reverse(nodes.begin(), nodes.end());
    for (auto x : nodes) {
      if (f(x)) {
        while (x->r > x->l) {
          assert(f(x));
          PushDown(x);
          if (x->rch && f(x->rch)) {
            x = x->rch;
          } else {
            x = x->lch;
          }
        }
        return x->l;
      }
    }
    return -1;
  }

  template <typename F>
  void TranverseLeaf(Node* x, F f) {
    if (!x) return;
    if (x->l == x->r) {
      f(x);
      return;
    }
    PushDown(x);
    TranverseLeaf(x->lch, f);
    TranverseLeaf(x->rch, f);
  };

  template <typename F>
  void TranverseAllNode(Node* x, F f) {
    if (!x) return;
    f(x);
    if (x->l < x->r) PushDown(x);
    TranverseAllNode(x->lch, f);
    TranverseAllNode(x->rch, f);
  }

  template <typename F>
  static Node* BuildTree(int l, int r, F f) {
    Node* x = new Node(l, r);
    if (l == r) {
      f(l, x);
      return x;
    }
    int m = l + (r - l) / 2;
    x->lch = BuildTree(l, m, f);
    x->rch = BuildTree(m + 1, r, f);
    x->Update();
    return x;
  }

  void GC(Node* x) {
    if (!x) return;
    GC(x->lch);
    GC(x->rch);
    delete x;
  }
};

pair<array<array<int, 3>, 2>, int> Plus(array<array<int, 3>, 2>& a, int lena,
                                        array<array<int, 3>, 2>& b, int lenb) {
  array<array<int, 3>, 2> res;
  for (int i = 0; i < 2; i++) {
    res[i][0] = a[i][0];
    if (a[i][0] == lena) res[i][0] = a[i][0] + b[i][0];
    res[i][1] = b[i][1];
    if (b[i][1] == lenb) res[i][1] = b[i][1] + a[i][1];
    res[i][2] = max(a[i][2], b[i][2]);
    ckmax(res[i][2], max(res[i][0], res[i][1]));
    ckmax(res[i][2], a[i][1] + b[i][0]);
  }
  return {res, lena + lenb};
}

struct Info {
  array<array<int, 3>, 2> data;
  int len;
  bool tag;
  void Flip() {
    tag ^= 1;
    swap(data[0], data[1]);
  }
  auto Node() { return reinterpret_cast<SegmentTree<Info>::Node*>(this); }
  Info() : tag(false) {}
  bool NeedPushDown() { return tag; }
  void PushDown() {
    auto lch = Node()->lch, rch = Node()->rch;
    lch->Flip();
    rch->Flip();
    tag = false;
  }
  void Update() {
    auto lch = Node()->lch, rch = Node()->rch;
    tie(data, len) = Plus(lch->data, lch->len, rch->data, rch->len);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  SegmentTree<Info> seg(0, n - 1);
  seg.root = seg.BuildTree(0, n - 1, [&](int i, Info* info) {
    int t = s[i] - '0';
    info->data[t][0] = info->data[t][1] = info->data[t][2] = 1;
    info->data[t ^ 1][0] = info->data[t ^ 1][1] = info->data[t ^ 1][2] = 0;
    info->len = 1;
  });
  while (q--) {
    int op, l, r;
    cin >> op >> l >> r;
    l--, r--;
    if (op == 1) {
      seg.Modify(l, r, [&](Info* info) { info->Flip(); });
    } else {
      array<array<int, 3>, 2> res = {{{{0, 0, 0}}, {{0, 0, 0}}}};
      int len = 0;
      for (auto node : seg.GetAllNodes(l, r)) {
        tie(res, len) = Plus(res, len, node->data, node->len);
      }
      cout << res[1][2] << '\n';
    }
  }

  return 0;
}

Submission Info

Submission Time
Task F - Vacation Query
User xindubawukong
Language C++ 20 (gcc 12.2)
Score 550
Code Size 6915 Byte
Status AC
Exec Time 212 ms
Memory 81856 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 550 / 550
Status
AC × 1
AC × 17
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 03_min_00.txt, 04_max_00.txt, 05_corner_00.txt, 05_corner_01.txt, 05_corner_02.txt, 05_corner_03.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3524 KiB
01_small_00.txt AC 24 ms 3508 KiB
01_small_01.txt AC 27 ms 3524 KiB
01_small_02.txt AC 2 ms 3740 KiB
01_small_03.txt AC 2 ms 3708 KiB
01_small_04.txt AC 2 ms 3716 KiB
02_random_00.txt AC 212 ms 81696 KiB
02_random_01.txt AC 173 ms 54864 KiB
02_random_02.txt AC 202 ms 81748 KiB
02_random_03.txt AC 132 ms 52520 KiB
02_random_04.txt AC 211 ms 81856 KiB
03_min_00.txt AC 17 ms 3640 KiB
04_max_00.txt AC 65 ms 81752 KiB
05_corner_00.txt AC 139 ms 81692 KiB
05_corner_01.txt AC 141 ms 81736 KiB
05_corner_02.txt AC 130 ms 81720 KiB
05_corner_03.txt AC 98 ms 81816 KiB