結果
問題 | No.905 Sorted? |
ユーザー |
![]() |
提出日時 | 2019-10-11 22:49:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,468 bytes |
コンパイル時間 | 1,662 ms |
コンパイル使用メモリ | 182,304 KB |
実行使用メモリ | 22,164 KB |
最終ジャッジ日時 | 2024-11-25 08:49:11 |
合計ジャッジ時間 | 5,384 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 WA * 4 RE * 9 |
ソースコード
#include <bits/stdc++.h>template <typename T>struct sparse_table {using size_t = std::size_t;template <typename U>using vector = std::vector<U>;size_t sz;vector<vector<size_t>> min;vector<size_t> log2;sparse_table() {}template <typename iterator>sparse_table(iterator first, iterator last): sz(distance(first, last)), min(1, vector<size_t>(sz)) {initialize(first);}template <typename iterator>void initialize(iterator dat) {log2.resize(sz + 2);log2[1] = 0;for (size_t i = 2; i < sz + 2; ++i) {log2[i] = log2[i / 2] + 1;}if (sz) min.reserve(log2[(sz + 1) / 2] + 2);std::iota(min[0].begin(), min[0].end(), 0);for (size_t i = 1; i < 30; ++i) {size_t w = 1 << i;if (sz + 1 < w) break;vector<size_t> next(sz + 1 - w);for (size_t l = 0; l < sz + 1 - w; ++l) {size_t left = min[i - 1][l], right = min[i - 1][l + w / 2];next[l] = dat[left] < dat[right] ? left : right;}min.emplace_back(move(next));}}template <typename Container>size_t rmq(Container const &x, size_t l, size_t r) const {size_t i = log2[r - l];size_t rr = r - (1 << i);l = min[i][l], r = min[i][rr];return x[l] < x[r] ? l : r;}};using namespace std;using ll = long long;#define int llvector<int> solve(const vector<int> &a, const vector<pair<int, int>> &qs) {int n = a.size();vector<int> ds;for (int i = 1; i < n; ++i) {ds.push_back(a[i] - a[i - 1]);}const auto st = sparse_table<int>(ds.begin(), ds.end());vector<int> ans;for (auto q : qs) {int l, r;tie(l, r) = q;int idx = st.rmq(ds, l, r);ans.push_back(ds[idx] >= 0 ? 1 : 0);}return ans;}signed main() {int n;cin >> n;vector<int> a(n);// forall non-negative? non-positive?for (int i = 0; i < n; ++i) {cin >> a[i];}int q;cin >> q;vector<pair<int, int>> qs(n);for (int i = 0; i < q; ++i) {int l, r;cin >> l >> r;qs[i] = make_pair(l, r);}vector<int> xs = solve(a, qs);for (auto &x : a) x = -x;vector<int> ys = solve(a, qs);for (int i = 0; i < q; ++i) {cout << xs[i] << ' ' << ys[i] << '\n';}}