| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 499390 |
2021-12-28T10:31:19 Z |
daidailanlan |
Deda (COCI17_deda) |
C++17 |
|
128 ms |
9500 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
128 ms |
9500 KB |
Output is correct |
| 5 |
Correct |
78 ms |
5140 KB |
Output is correct |
| 6 |
Correct |
78 ms |
9336 KB |
Output is correct |
| 7 |
Correct |
91 ms |
9444 KB |
Output is correct |
