| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 499389 |
2021-12-28T10:29:19 Z |
daidailanlan |
Deda (COCI17_deda) |
C++17 |
|
146 ms |
13040 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
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
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
272 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
2 ms |
304 KB |
Output is correct |
| 4 |
Correct |
146 ms |
13040 KB |
Output is correct |
| 5 |
Correct |
115 ms |
8364 KB |
Output is correct |
| 6 |
Correct |
132 ms |
12792 KB |
Output is correct |
| 7 |
Correct |
143 ms |
12876 KB |
Output is correct |
