結果

問題 No.905 Sorted?
ユーザー tubo28tubo28
提出日時 2019-10-11 23:00:32
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 5 ms
6,820 KB
testcase_06 AC 4 ms
6,820 KB
testcase_07 AC 9 ms
6,816 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 114 ms
17,956 KB
testcase_12 AC 124 ms
17,400 KB
testcase_13 AC 177 ms
21,664 KB
testcase_14 AC 177 ms
21,608 KB
testcase_15 AC 124 ms
22,068 KB
testcase_16 WA -
testcase_17 RE -
testcase_18 AC 146 ms
21,468 KB
testcase_19 RE -
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,816 KB
testcase_22 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

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';
    }
}
0