Submission #499389

#	Time	Username	Problem	Language	Result	Execution time	Memory
499389		daidailanlan	Deda (COCI17_deda)	C++17	140 / 140	146 ms	13040 KiB

deda

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
namespace math {
inline uint32_t nextPow2_32(uint32_t v) {
  if (!v) {
    return 1;
  }
  uint32_t res = 1U << (31 ^ __builtin_clz(v));
  return res == v ? res : res << 1;
}
} // namespace math
namespace ds {
template<typename V, typename InitV = V, typename Update = InitV, typename TraverseArgs = nullptr_t>
struct BaseLazyCompactSegmentTree {
  struct Node {
    V v;
    Update update;
    int lower, upper;
    inline bool isValid() const {
      return lower < upper;
    }
    inline bool isLeaf() const {
      return lower + 1 == upper;
    }
  };
  enum Traverse { NONE, LEFT, RIGHT, ALL };
  virtual inline Traverse _traverse(Node& node, int lower, int upper, TraverseArgs& args) {
    return Traverse::NONE;
  }
  virtual inline bool _hasUpdate(Node& node) = 0;
  virtual inline void _applyUpdate(const Update& update, Node& node) = 0;
  virtual inline void _clearUpdate(Node& node) = 0;
  virtual inline void _initV(InitV initV, Node& node) = 0;
  virtual inline void _mergeV(const Node& lNode, const Node& rNode, V& res) = 0;
  inline void init(vector<InitV> initVs) {
    int n = static_cast<int>((initVs).size());
    _offset = math::nextPow2_32(n);
    _offsetBit = __builtin_ctz(_offset);
    _nodes.resize(_offset << 1);
    for (int i = (0); i < (n); ++i) {
      auto& node = _nodes[_offset + i];
      node.lower = i;
      node.upper = i + 1;
      _clearUpdate(node);
      _initV(move(initVs[i]), node);
    }
    for (int i = (n); i < (_offset); ++i) {
      auto& node = _nodes[_offset + i];
      node.lower = -1;
      node.upper = -2;
    }
    for (int i = (_offset - 1); i >= (1); --i) {
      auto& node = _nodes[i];
      const auto &lNode = _nodes[i << 1], rNode = _nodes[(i << 1) | 1];
      if (lNode.upper == rNode.lower) {
        node.lower = lNode.lower;
        node.upper = rNode.upper;
        _clearUpdate(node);
        _mergeV(lNode, rNode, node.v);
      } else {
        node.lower = -1;
        node.upper = -2;
      }
    }
  }
  inline void updateRange(int lower, int upper, const Update& update) {
    lower += _offset;
    upper += _offset;
    int lowerCtz1 = __builtin_ctz(lower) + 1, upperCtz1 = __builtin_ctz(upper) + 1,
        commonCtz1 = max(lowerCtz1, upperCtz1);
    for (int i = (_offsetBit); i >= (commonCtz1); --i) {
      _push(lower >> i);
      _push((upper - 1) >> i);
    }
    for (int i = (commonCtz1 - 1); i >= (lowerCtz1); --i) {
      _push(lower >> i);
    }
    for (int i = (commonCtz1 - 1); i >= (upperCtz1); --i) {
      _push((upper - 1) >> i);
    }
    for (int l = lower, u = upper; l < u; l >>= 1, u >>= 1) {
      if (l & 1) {
        _applyUpdateWrapper(update, _nodes[l++]);
      }
      if (u & 1) {
        _applyUpdateWrapper(update, _nodes[--u]);
      }
    }
    for (int i = (lowerCtz1); i < (commonCtz1); ++i) {
      _mergeVWrapper(lower >> i);
    }
    for (int i = (upperCtz1); i < (commonCtz1); ++i) {
      _mergeVWrapper((upper - 1) >> i);
    }
    for (int i = commonCtz1; i <= _offsetBit; ++i) {
      _mergeVWrapper(lower >> i);
      _mergeVWrapper((upper - 1) >> i);
    }
  }
  inline void traverseRange(int lower, int upper, TraverseArgs& args) {
    int lower2 = lower + _offset;
    int upper2 = upper + _offset;
    int lowerCtz1 = __builtin_ctz(lower2) + 1, upperCtz1 = __builtin_ctz(upper2) + 1,
        commonCtz1 = max(lowerCtz1, upperCtz1);
    for (int i = (_offsetBit); i >= (commonCtz1); --i) {
      _push(lower2 >> i);
      _push((upper2 - 1) >> i);
    }
    for (int i = (commonCtz1 - 1); i >= (lowerCtz1); --i) {
      _push(lower2 >> i);
    }
    for (int i = (commonCtz1 - 1); i >= (upperCtz1); --i) {
      _push((upper2 - 1) >> i);
    }
    int bit = 0;
    for (int l = lower2; l < (upper2 >> bit); ++bit, l >>= 1) {
      if (l & 1) {
        _traverseWrapper(l++, lower, upper, args);
      }
    }
    for (--bit; bit >= 0; --bit) {
      int u = upper2 >> bit;
      if (u & 1) {
        _traverseWrapper(u ^ 1, lower, upper, args);
      }
    }
    for (int i = (lowerCtz1); i < (commonCtz1); ++i) {
      _mergeVWrapper(lower2 >> i);
    }
    for (int i = (upperCtz1); i < (commonCtz1); ++i) {
      _mergeVWrapper((upper2 - 1) >> i);
    }
    for (int i = commonCtz1; i <= _offsetBit; ++i) {
      _mergeVWrapper(lower2 >> i);
      _mergeVWrapper((upper2 - 1) >> i);
    }
  }
  inline void _push(int idx) {
    auto& node = _nodes[idx];
    if (!node.isValid() || node.isLeaf() || !_hasUpdate(node)) {
      return;
    }
    _applyUpdate(node.update, _nodes[idx << 1]);
    _applyUpdate(node.update, _nodes[(idx << 1) | 1]);
    _clearUpdate(node);
  }
  inline void _mergeVWrapper(int idx) {
    auto& node = _nodes[idx];
    if (node.isValid()) {
      _mergeV(_nodes[idx << 1], _nodes[(idx << 1) | 1], node.v);
    }
  }
  inline void _applyUpdateWrapper(const Update& update, Node& node) {
    if (node.isValid()) {
      _applyUpdate(update, node);
    }
  }
  inline void _traverseWrapper(int idx, int lower, int upper, TraverseArgs& args) {
    auto& node = _nodes[idx];
    Traverse traverse = _traverse(node, lower, upper, args);
    if (traverse == Traverse::NONE || node.isLeaf()) {
      return;
    }
    if (_hasUpdate(node)) {
      _applyUpdate(node.update, _nodes[idx << 1]);
      _applyUpdate(node.update, _nodes[(idx << 1) | 1]);
      _clearUpdate(node);
    }
    if (traverse != Traverse::RIGHT) {
      _traverseWrapper(idx << 1, lower, upper, args);
    }
    if (traverse != Traverse::LEFT) {
      _traverseWrapper((idx << 1) | 1, lower, upper, args);
    }
    _mergeV(_nodes[idx << 1], _nodes[(idx << 1) | 1], node.v);
  }
  int _offset, _offsetBit;
  vector<Node> _nodes;
};
} // namespace ds
int threshold;
struct LazyCompactSegmentTreeStops : ds::BaseLazyCompactSegmentTree<int, int, int, int> {
  using V = int;
  using InitV = int;
  using Update = int;
  using TraverseArgs = int;
  using Node = typename LazyCompactSegmentTreeStops::Node;
  inline bool _hasUpdate(Node& node) override {
    return false;
  }
  inline void _applyUpdate(const Update& update, Node& node) override {
    node.v = update;
  }
  inline void _clearUpdate(Node& node) override {}
  inline void _initV(InitV initV, Node& node) override {
    node.v = initV;
  }
  inline void _mergeV(const Node& lNode, const Node& rNode, V& res) override {
    res = min(lNode.v, rNode.v);
  }
  inline Traverse _traverse(Node& node, int lower, int upper, TraverseArgs& args) override {
    if (args >= 0 || node.v > threshold) {
      return Traverse::NONE;
    }
    if (node.isLeaf()) {
      args = node.lower + 1;
      return Traverse::NONE;
    }
    int idx = &node - _nodes.data();
    return _nodes[idx << 1].v <= threshold ? Traverse::LEFT : Traverse::RIGHT;
  }
};
const int INF = 1000000000 + 1;
char op[2];
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  LazyCompactSegmentTreeStops st;
  st.init(vector<int>(n, INF));
  for (int _ = (0); _ < (q); ++_) {
    int cnt, idx;
    scanf("%s%d%d", op, &cnt, &idx);
    --idx;
    if (op[0] == 'M') {
      st.updateRange(idx, idx + 1, cnt);
    } else {
      threshold = cnt;
      int res = -1;
      st.traverseRange(idx, n, res);
      printf("%d\n", res);
    }
  }
  return 0;
}

Compilation message (stderr)

deda.cpp: In function 'int main()':
deda.cpp:239:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  239 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
deda.cpp:244:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |     scanf("%s%d%d", op, &cnt, &idx);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140