#define _GLIBCXX_DEBUG
// https://oj.uz/problem/view/JOI14_fortune_telling2
#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif
#include <cassert>
#include <cstdio>
#include <vector>
#include <functional>
#include <cstddef>
#include <algorithm>
template <class T> struct RMQ {
public:
std::function<T(T, T)> const min_f;
RMQ (std::function<T(T, T)> _min_f) : min_f (_min_f) {}
T get(size_t left, size_t right) {
#ifdef _GLIBCXX_DEBUG
#ifdef NDEBUG
static_assert(false, "_GLIBCXX_DEBUG and NDEBUG both defined -- conflict");
#endif // NDEBUG
T result = __get(left, right);
T ans = __data[left];
for (size_t i = left + 1; i < right; ++i) ans = min_f(ans, __data[i]);
assert(ans == result);
return ans;
}
T __get(size_t left, size_t right) {
#endif // _GLIBCXX_DEBUG
assert(right > left);
assert(0 <= left); assert(right <= sparse_array[0].size());
size_t len = right - left;
size_t constexpr nbit_1 = sizeof(size_t) * 8 - 1;
static_assert(nbit_1 + 1 != 0, "size_t doesn't have any size");
size_t rmq_i = nbit_1 - __builtin_clz(len);
T result = min_f(sparse_array[rmq_i][left], sparse_array[rmq_i][right - (1 << rmq_i)]);
assert(result == sparse_array[rmq_i][left] || result == sparse_array[rmq_i][right - (1 << rmq_i)]);
return result;
}
void reset(std::vector<T> data) {
#ifdef _GLIBCXX_DEBUG
__data = data;
#endif // _GLIBCXX_DEBUG
size_t n = data.size();
sparse_array.clear();
sparse_array.push_back(std::move(data));
while (true) { // so array size is > 0
size_t index = sparse_array.size();
if (n < (1u << index)) break; // n+1 <= ... <==> n < ...
sparse_array.push_back(std::vector<T>(n - (1 << index) + 1));
for (size_t i = 0; i < sparse_array[index].size(); ++i)
sparse_array[index][i] = min_f(sparse_array[index-1][i],
sparse_array[index-1][i+(1<<(index-1))]);
}
}
// private:
#ifdef _GLIBCXX_DEBUG
std::vector<T> __data;
#endif // _GLIBCXX_DEBUG
std::vector<std::vector<T>> sparse_array;
};
template <typename T> struct FT {
std::vector<T> tree;
FT(int n) {
tree.assign(n + 1, 0); // tree[0] is not used
}
void update(size_t pos, T val) {
++pos;
while (pos > 0) {
tree[pos] += val;
pos -= pos & -pos;
}
}
/// Get the sum of all values from pos to end of tree.
T get(size_t pos) {
T result = 0;
++pos;
while (pos < tree.size()) {
result += tree[pos];
pos += pos & -pos;
}
return result;
}
};
int main() {
std::vector<int> values;
long long ans = 0;
//{ ------ Take input ------
int ncard, noperation;
std::scanf("%d %d", &ncard, &noperation);
std::vector<std::pair<int, int>> cards; cards.reserve(ncard);
for (int i = 0; i < ncard; ++i) {
int u, v;
std::scanf("%d %d", &u, &v);
if (u != v) {
cards.emplace_back(u, v);
values.push_back(u);
values.push_back(v);
} else {
ans += u;
}
}
std::vector<int> operations (noperation);
for (int& o : operations) {
std::scanf("%d", &o);
values.push_back(o);
}
//}
// ------- Refine coordinates and calculate -------
std::sort(values.begin(), values.end());
values.erase(std::unique(values.begin(), values.end()), values.end());
#define refine(x) x = std::lower_bound(values.begin(), values.end(), x) - values.begin()
std::vector<int> last_operation_at (values.size(), -1);
for (size_t op_i = 0; op_i < operations.size(); ++op_i) {
refine(operations[op_i]);
last_operation_at[operations[op_i]] = (int)op_i;
}
RMQ<int> last_operation_in_range ( [](int x, int y)->int{return std::max(x, y);} );
last_operation_in_range.reset(last_operation_at);
struct query_t {
int front_val, back_val, first_operation;
};
std::vector<query_t> queries;
for (auto& card : cards) {
int u = card.first, v = card.second; // u = first state
refine(u); refine(v);
int min = std::min(u, v), max = std::max(u, v);
// operations in range [min, max) force the value to become [max]
int last_op = last_operation_in_range.get(min, max); // [min..max) range
if (last_op == -1) {
queries.push_back({u, v, 0});
} else if (last_op != noperation - 1) {
queries.push_back({max, min, last_op + 1});
} else {
ans += values[max]; // no more operations after the assignment one
}
}
std::vector<std::vector<int>>{}.swap(last_operation_in_range.sparse_array);
std::sort(queries.begin(), queries.end(), [](query_t const & x, query_t const & y)->bool{
return x.first_operation < y.first_operation ;
}); // process the last (back) operations first
FT<int> n_operation_with_height (values.size());
for (size_t op_i = operations.size(); op_i --> 0;) {
n_operation_with_height.update(operations[op_i], 1);
while (!queries.empty() && queries.back().first_operation == (int)op_i) {
query_t q = queries.back(); queries.pop_back();
ans += values[(n_operation_with_height.get(std::max(q.front_val, q.back_val)) % 2 == 0) ? q.front_val : q.back_val];
}
}
assert(queries.empty());
std::printf("%LLd\n", ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:190:27: warning: unknown conversion type character 'L' in format [-Wformat=]
std::printf("%LLd\n", ans);
^
fortune_telling2.cpp:190:27: warning: too many arguments for format [-Wformat-extra-args]
fortune_telling2.cpp:111:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
std::scanf("%d %d", &ncard, &noperation);
^
fortune_telling2.cpp:115:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
std::scanf("%d %d", &u, &v);
^
fortune_telling2.cpp:127:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
std::scanf("%d", &o);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
2156 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
286 ms |
4212 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
4848 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
