Submission #967075

#	Time	Username	Problem	Language	Result	Execution time	Memory
967075		kilkuwu	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1047 ms	229844 KiB

street_lamps

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

struct SegmentTreeX {
  struct SegmentTreeY {
    struct Node {
      int v = 0, l = 0, r = 0;
    };

    std::vector<Node> tree = {Node(), Node()};

    int add_node() {
      tree.emplace_back();
      return tree.size() - 1;
    }

    void update(int k, int l, int r, int ql, int qr, int qv) {
      if (ql <= l && r <= qr) {
        tree[k].v += qv;
        return;
      }

      int m = (l + r) / 2;
      if (m >= ql) { // (l, m)
        if (tree[k].l == 0) tree[k].l = add_node();
        update(tree[k].l, l, m, ql, qr, qv);
      }
      if (m + 1 <= qr) {
        if (tree[k].r == 0) tree[k].r = add_node();
        update(tree[k].r, m + 1, r, ql, qr, qv);
      }
    }

    int query(int k, int l, int r, int qp) {
      int ans = tree[k].v;
      if (l == r) {
        return ans;
      }

      int m = (l + r) / 2;
      if (qp <= m) {
        return ans + query(tree[k].l, l, m, qp);
      }
      return ans + query(tree[k].r, m + 1, r, qp);
    }
  };

  int n;
  std::vector<SegmentTreeY> tree;

  SegmentTreeX(int _n) : n(_n), tree(4 * n) {}

  void update(int k, int l, int r, int ql, int qr, int ly, int ry, int qv) {
    if (ql <= l && r <= qr) {
      tree[k].update(1, 0, n - 1, ly, ry, qv);
      return;
    }

    int m = (l + r) / 2;
    if (m >= ql) {  // (l, m)
      update(k << 1, l, m, ql, qr, ly, ry, qv);
    }
    if (m + 1 <= qr) {
      update(k << 1 | 1, m + 1, r, ql, qr, ly, ry, qv);
    }
  }

  int query(int k, int l, int r, int qpx, int qpy) {
    int ans = tree[k].query(1, 0, n - 1, qpy);
    if (l == r) {
      return ans;
    }

    int m = (l + r) / 2;
    if (qpx <= m) {
      return ans + query(k << 1, l, m, qpx, qpy);
    }
    return ans + query(k << 1 | 1, m + 1, r, qpx, qpy);
  }
};

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

  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    char c; std::cin >> c;
    a[i] = c - '0';
  }
  
  std::set<std::pair<int, int>> ranges;

  for (int i = 0; i < n; i++) {
    if (a[i] == 0) continue;
    int j = i;
    while (j < n && a[j] == 1) {
      j++;
    }
    ranges.emplace(i, j); // [i, j) full of ones
    i = j;
  }

  auto find_contain_and_toggle = [&](int i) -> std::pair<int, int> {
    auto it = ranges.upper_bound({i, std::numeric_limits<int>::max()}); // {{i, i+1}, ...}
    assert(it != ranges.begin());
    --it;
    auto res = *it;
    ranges.erase(it);
    if (res.first < i) { 
      ranges.emplace(res.first, i);
    }
    if (i + 1 < res.second) {
      ranges.emplace(i + 1, res.second);
    }
    return res;
  };

  auto find_left_right_and_toggle = [&](int i) -> std::pair<int, int> {
    auto it = ranges.upper_bound({i, i + 1});
    int l = i, r = i + 1;
    if (it != ranges.end()) {
      if (it->first == i + 1) {
        r = it->second;
        it = ranges.erase(it);
      }
    } 
    if (it != ranges.begin()) {
      --it;
      if (it->second == i) {
        l = it->first;
        it = ranges.erase(it);
      }
    }

    ranges.emplace(l, r);
    return {l, r};
  };

  auto check_range = [&](int l, int r) -> bool {
    auto it = ranges.upper_bound({l, std::numeric_limits<int>::max()});
    if (it == ranges.begin()) return false;
    --it;
    return r < it->second;
  };

  SegmentTreeX tree(n);

  for (int i = 1; i <= q; i++) {
    std::string com;
    std::cin >> com;
    if (com[0] == 't') {
      int id;
      std::cin >> id;
      --id;
      if (a[id] == 0) {
        auto [l, r] = find_left_right_and_toggle(id);
        tree.update(1, 0, n - 1, l, id, id, r - 1, -i);
      } else {
        auto [l, r] = find_contain_and_toggle(id);
        tree.update(1, 0, n - 1, l, id, id, r - 1, i);
      }
      a[id] ^= 1;
    } else {
      int l, r;
      std::cin >> l >> r;
      l--, r -= 2;
      // query value of (a, b)  
      // get value of a, b 
      int ans = i * check_range(l, r);
      ans += tree.query(1, 0, n - 1, l, r);
      std::cout << ans << nl;

    }
  }
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20