Submission #36007

#	Time	Username	Problem	Language	Result	Execution time	Memory
36007		user202729	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	2000 ms	4848 KiB

fortune_telling2

#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 (stderr)

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);
                       ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65