Submission #499390

#	Time	Username	Problem	Language	Result	Execution time	Memory
499390		daidailanlan	Deda (COCI17_deda)	C++17	140 / 140	128 ms	9500 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
namespace io {
const int _kReadBufferSize = 1 << 15;
char _readBuffer[_kReadBufferSize];
int _readPos;
int _readLength;
bool _ended = false;
inline void _loadBuffer() {
  _readLength = static_cast<int>(fread(_readBuffer, sizeof(char), _kReadBufferSize, stdin));
  _readPos = 0;
}
inline char readChar(bool advance = true) {
  if (_ended) {
    return 0;
  }
  if (_readPos >= _readLength) {
    _loadBuffer();
    if (_readLength == 0) {
      _ended = true;
      return 0;
    }
  }
  return _readBuffer[advance ? _readPos++ : _readPos];
}
inline int readCharArray(char* s) {
  char ch;
  while (true) {
    ch = readChar(false);
    if (!ch) {
      return 0;
    }
    if (!isspace(ch)) {
      break;
    }
    ++_readPos;
  }
  *s++ = readChar(true);
  int res = 1;
  while (true) {
    ch = readChar(false);
    if (!ch) {
      return res;
    }
    if (isspace(ch)) {
      break;
    }
    *s++ = ch;
    ++res;
    ++_readPos;
  }
  *s = '\0';
  return res;
}
template<typename T>
inline bool readInt(T& res) {
  char ch;
  while (true) {
    ch = readChar(false);
    if (!ch) {
      return false;
    }
    if (!isspace(ch)) {
      break;
    }
    ++_readPos;
  }
  ch = readChar(false);
  bool negative = ch == '-';
  if (negative) {
    ++_readPos;
  }
  res = 0;
  while (true) {
    ch = readChar(false);
    if (!isdigit(ch)) {
      break;
    }
    res = (res << 3) + (res << 1) + (ch & 15);
    ++_readPos;
  }
  if (negative) {
    res = -res;
  }
  return true;
}
const int _kWriteBufferSize = 1 << 15;
int _writePos = 0;
char _writeBuffer[_kWriteBufferSize];
inline void writeChar(char x) {
  if (_writePos == _kWriteBufferSize) {
    fwrite(_writeBuffer, 1, _kWriteBufferSize, stdout);
    _writePos = 0;
  }
  _writeBuffer[_writePos++] = x;
}
struct _Flusher {
  inline void flush() {
    if (_writePos) {
      fwrite(_writeBuffer, 1, _writePos, stdout);
      _writePos = 0;
    }
    fflush(stdout);
  }
  inline ~_Flusher() {
    flush();
  }
} _flusher;
template<class T>
inline void writeInt(T x, char c = 0, int padding = 0) {
  static char s[32];
  if (x < 0) {
    writeChar('-');
    x = -x;
  }
  int n = 0;
  while (x || !n) {
    T newX = x / 10;
    s[n++] = '0' + (x - (newX << 3) - (newX << 1));
    x = newX;
  }
  for (int i = n; i < padding; ++i) {
    writeChar('0');
  }
  for (; n > 0; writeChar(s[--n])) {}
  if (c) {
    writeChar(c);
  }
}
} // namespace io
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;
  io::readInt(n);
  io::readInt(q);
  LazyCompactSegmentTreeStops st;
  st.init(vector<int>(n, INF));
  for (int _ = (0); _ < (q); ++_) {
    int cnt, idx;
    io::readCharArray(op);
    io::readInt(cnt);
    io::readInt(idx);
    --idx;
    if (op[0] == 'M') {
      st.updateRange(idx, idx + 1, cnt);
    } else {
      threshold = cnt;
      int res = -1;
      st.traverseRange(idx, n, res);
      io::writeInt(res, '\n');
    }
  }
  return 0;
}

• Subtask 1: 140 / 140