Skip to content

3161. Block Placement Queries 👍

  • Time: $O(10^5 + n\log 10^5)$
  • Space: $O(10^5 + q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class FenwickTree {
 public:
  FenwickTree(int n) : vals(n + 1) {}

  void maximize(int i, int val) {
    while (i < vals.size()) {
      vals[i] = max(vals[i], val);
      i += lowbit(i);
    }
  }

  int get(int i) const {
    int res = 0;
    while (i > 0) {
      res = max(res, vals[i]);
      i -= lowbit(i);
    }
    return res;
  }

 private:
  vector<int> vals;

  static int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  vector<bool> getResults(vector<vector<int>>& queries) {
    const int n = min(50000, static_cast<int>(queries.size()) * 3);
    vector<bool> ans;
    FenwickTree tree(n + 1);
    set<int> obstacles{0, n};  // sentinel values

    for (const vector<int>& query : queries) {
      const int type = query[0];
      if (type == 1) {
        const int x = query[1];
        obstacles.insert(x);
      }
    }

    for (auto it = obstacles.begin(); std::next(it) != obstacles.end(); ++it) {
      const int x1 = *it;
      const int x2 = *std::next(it);
      tree.maximize(x2, x2 - x1);
    }

    for (int i = queries.size() - 1; i >= 0; --i) {
      const int type = queries[i][0];
      const int x = queries[i][1];
      if (type == 1) {
        const auto it = obstacles.find(x);
        if (next(it) != obstacles.end())  // x is not the last element.
          tree.maximize(*next(it), *next(it) - *prev(it));
        obstacles.erase(it);
      } else {
        const int sz = queries[i][2];
        const auto it = obstacles.upper_bound(x);
        const int prev = *std::prev(it);
        ans.push_back(tree.get(prev) >= sz || x - prev >= sz);
      }
    }

    ranges::reverse(ans);
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class FenwickTree {
  public FenwickTree(int n) {
    vals = new int[n + 1];
  }

  public void add(int i, int val) {
    while (i < vals.length) {
      vals[i] = Math.max(vals[i], val);
      i += lowbit(i);
    }
  }

  public int get(int i) {
    int res = 0;
    while (i > 0) {
      res = Math.max(res, vals[i]);
      i -= lowbit(i);
    }
    return res;
  }

  private int[] vals;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public List<Boolean> getResults(int[][] queries) {
    final int n = Math.min(50000, queries.length * 3);
    List<Boolean> ans = new ArrayList<>();
    FenwickTree tree = new FenwickTree(n + 1);
    TreeSet<Integer> obstacles = new TreeSet<>(Arrays.asList(0, n)); // sentinel values

    for (int[] query : queries) {
      final int type = query[0];
      if (type == 1) {
        final int x = query[1];
        obstacles.add(x);
      }
    }

    Iterator<Integer> it = obstacles.iterator();
    int x1 = it.next();
    while (it.hasNext()) {
      final int x2 = it.next();
      tree.add(x2, x2 - x1);
      x1 = x2;
    }

    for (int i = queries.length - 1; i >= 0; --i) {
      final int type = queries[i][0];
      final int x = queries[i][1];
      if (type == 1) {
        final Integer next = obstacles.higher(x);
        final Integer prev = obstacles.lower(x);
        if (next != null)
          tree.add(next, next - prev);
        obstacles.remove(x);
      } else {
        final int sz = queries[i][2];
        final int prev = obstacles.floor(x);
        ans.add(tree.get(prev) >= sz || x - prev >= sz);
      }
    }

    Collections.reverse(ans);
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from sortedcontainers import SortedList


class FenwickTree:
  def __init__(self, n: int):
    self.vals = [0] * (n + 1)

  def maximize(self, i: int, val: int) -> None:
    while i < len(self.vals):
      self.vals[i] = max(self.vals[i], val)
      i += FenwickTree.lowtree(i)

  def get(self, i: int) -> int:
    res = 0
    while i > 0:
      res = max(res, self.vals[i])
      i -= FenwickTree.lowtree(i)
    return res

  @staticmethod
  def lowtree(i: int) -> int:
    return i & -i


class Solution:
  def getResults(self, queries: list[list[int]]) -> list[bool]:
    n = min(50000, len(queries) * 3)
    ans = []
    tree = FenwickTree(n + 1)
    obstacles = SortedList([0, n])  # sentinel values

    for query in queries:
      type = query[0]
      if type == 1:
        x = query[1]
        obstacles.add(x)

    for x1, x2 in itertools.pairwise(obstacles):
      tree.maximize(x2, x2 - x1)

    for query in reversed(queries):
      type = query[0]
      x = query[1]
      if type == 1:
        i = obstacles.index(x)
        next = obstacles[i + 1]
        prev = obstacles[i - 1]
        obstacles.remove(x)
        tree.maximize(next, next - prev)
      else:
        sz = query[2]
        i = obstacles.bisect_right(x)
        prev = obstacles[i - 1]
        ans.append(tree.get(prev) >= sz or x - prev >= sz)

    return ans[::-1]