oj.uz

Submission #967067

# Submission time Handle Problem Language Result Execution time Memory
967067 2024-04-21T05:34:36 Z kilkuwu Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1008 ms 233908 KB 
#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 *it;
  };

  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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 919 ms 233908 KB Output is correct
6 Correct 942 ms 207100 KB Output is correct
7 Correct 1008 ms 173388 KB Output is correct
8 Correct 774 ms 75288 KB Output is correct
9 Correct 102 ms 4140 KB Output is correct
10 Correct 97 ms 4176 KB Output is correct
11 Correct 109 ms 4444 KB Output is correct
12 Correct 803 ms 74032 KB Output is correct
13 Correct 773 ms 75284 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -