結果

問題 No.905 Sorted?
ユーザー tubo28
提出日時 2019-10-11 23:00:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,601 bytes
コンパイル時間 2,223 ms
コンパイル使用メモリ 188,608 KB
実行使用メモリ 22,068 KB
最終ジャッジ日時 2024-11-25 09:05:58
合計ジャッジ時間 5,159 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 12 WA * 9 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using ll = long long;
#define int ll
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;
vector<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 (auto &x : a) cin >> x;
{
map<int, int> mp;
for (auto &x : a) mp[x] = 0;
int i = 0;
for (auto &p : mp) p.second = i++;
for (auto &x : a) x = mp[x];
}
int q;
cin >> q;
vector<pair<int, int>> qs(q);
for (auto &q : qs) {
int l, r;
cin >> l >> r;
q = 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';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0