結果
問題 | No.875 Range Mindex Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 21:32:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 2,168 bytes |
コンパイル時間 | 2,222 ms |
コンパイル使用メモリ | 199,232 KB |
最終ジャッジ日時 | 2025-01-07 16:42:35 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:70:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘long int*’ [-Wformat=] 70 | scanf("%lld", &e); | ~~~^ ~~ | | | | | long int* | long long int* | %ld main.cpp:66:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 66 | scanf("%d%d", &N, &Q); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:70:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 70 | scanf("%lld", &e); | ~~~~~^~~~~~~~~~~~ main.cpp:81:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 81 | scanf("%d%d%d", &query, &l, &r); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> ///////////////////////// // Range Minimum Query // ///////////////////////// class RMinQ { private: std::vector<int64_t> container_; const int64_t inf_{LLONG_MAX}; void build(const unsigned int array_size) { unsigned int length{1}; while (length < array_size) length <<= 1; container_.resize(2 * length, inf_); } public: RMinQ(const unsigned int array_size) { build(array_size); } RMinQ(const std::vector<int64_t> &array) { build(array.size()); std::copy(array.begin(), array.end(), container_.begin() + (container_.size() >> 1)); for (auto i{(container_.size() >> 1) - 1}; i > 0; i--) container_[i] = std::min(container_[2 * i], container_[2 * i + 1]); } // indexは0-indexed void update(const int index, const int64_t assigned) { auto update_place{(container_.size() >> 1) + index}; container_[update_place] = assigned; while (update_place > 1) { update_place >>= 1; container_[update_place] = std::min(container_[2 * update_place], container_[2 * update_place + 1]); } } // left,rightは0-indexed、[left, right)の半開区間 int64_t get(const int left, const int right) const { int64_t min{inf_}; for (int left_i{std::max(0, left) + ((int)container_.size() >> 1)}, right_i{std::min((int)container_.size() >> 1, right) + ((int)container_.size() >> 1)}; left_i < right_i; left_i >>= 1, right_i >>= 1 ) { if (left_i & 1) { min = std::min(min, container_[left_i]); left_i++; } if (right_i & 1) { right_i--; min = std::min(min, container_[right_i]); } } return min; } }; int main() { int N, Q; scanf("%d%d", &N, &Q); std::vector<int64_t> a(N); for (auto& e: a) { scanf("%lld", &e); e--; } RMinQ rmq(a); std::vector<int> indices(N); for (int i{}; i < N; i++) indices[a[i]] = i; for (int i{}; i < Q; i++) { int query, l, r; scanf("%d%d%d", &query, &l, &r); l--; r--; if (query == 1) { rmq.update(l, a[r]); rmq.update(r, a[l]); std::swap(indices[a[l]], indices[a[r]]); std::swap(a[l], a[r]); } else { auto min{rmq.get(l, r + 1)}; printf("%d\n", indices[min] + 1); } } return 0; }