結果
問題 | No.878 Range High-Element Query |
ユーザー | 0w1 |
提出日時 | 2019-10-12 16:13:08 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 334 ms / 2,000 ms |
コード長 | 2,574 bytes |
コンパイル時間 | 2,345 ms |
コンパイル使用メモリ | 213,992 KB |
実行使用メモリ | 12,560 KB |
最終ジャッジ日時 | 2023-08-18 19:08:02 |
合計ジャッジ時間 | 6,122 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,060 KB |
testcase_01 | AC | 5 ms
5,116 KB |
testcase_02 | AC | 5 ms
5,284 KB |
testcase_03 | AC | 5 ms
5,168 KB |
testcase_04 | AC | 5 ms
5,068 KB |
testcase_05 | AC | 5 ms
5,108 KB |
testcase_06 | AC | 4 ms
5,112 KB |
testcase_07 | AC | 4 ms
5,288 KB |
testcase_08 | AC | 6 ms
5,196 KB |
testcase_09 | AC | 6 ms
5,116 KB |
testcase_10 | AC | 4 ms
5,200 KB |
testcase_11 | AC | 299 ms
11,024 KB |
testcase_12 | AC | 235 ms
11,504 KB |
testcase_13 | AC | 240 ms
9,752 KB |
testcase_14 | AC | 188 ms
9,072 KB |
testcase_15 | AC | 236 ms
11,092 KB |
testcase_16 | AC | 319 ms
12,344 KB |
testcase_17 | AC | 331 ms
12,560 KB |
testcase_18 | AC | 334 ms
12,400 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<int n, typename E, typename T, typename FTE, typename FTT, typename FEE> struct Segt { E ei; T ti; vector<E> dat; vector<T> tag; FTE fte; FTT ftt; FEE fee; Segt(E ei, T ti, FTE a, FTT b, FEE c) : ei(ei), ti(ti), fte(a), ftt(b), fee(c){ dat.assign(2 * n, ei); tag.assign(2 * n, ti); } void build(vector<E> a) { for (int i = 0; i < a.size(); ++i) dat[n + i] = a[i]; for (int i = n - 1; i; --i) dat[i] = fee(dat[i << 1], dat[i << 1 | 1]); } void push(int k) { for (int c = 0; c < 2; ++c) { tag[k << 1 | c] = ftt(tag[k], tag[k << 1 | c]); dat[k << 1 | c] = fte(tag[k], dat[k << 1 | c]); } tag[k] = ti; } void update(T t, int ql, int qr, int lb = 0, int rb = n, int k = 1) { if (qr <= lb || rb <= ql) return; if (ql <= lb && rb <= qr) { tag[k] = ftt(t, tag[k]); dat[k] = fte(t, dat[k]); return; } push(k); int mb = lb + rb >> 1; update(t, ql, qr, lb, mb, k << 1); update(t, ql, qr, mb, rb, k << 1 | 1); dat[k] = fee(dat[k << 1], dat[k << 1 | 1]); } E query(int ql, int qr, int lb = 0, int rb = n, int k = 1) { if (qr <= lb || rb <= ql) return ei; if (ql <= lb && rb <= qr) return dat[k]; push(k); int mb = lb + rb >> 1; return fee(query(ql, qr, lb, mb, k << 1), query(ql, qr, mb, rb, k << 1 | 1)); } }; int main() { ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } typedef struct { int minv; } E; typedef struct { int updv; } T; function<E(T, E)> fte = [](T f, E e) { return E({ f.updv ? f.updv : e.minv }); }; function<T(T, T)> ftt = [](T f, T t) { return T({ f.updv ? f.updv : t.updv }); }; function<E(E, E)> fee = [](E l, E r) { return E({ min(l.minv, r.minv) }); }; Segt<(1 << 17), E, T, decltype(fte), decltype(ftt), decltype(fee)> tree(E({N}), T({0}), fte, ftt, fee); vector<vector<int>> nxt2(17, vector<int>(N, N)); for (int i = N - 1; ~i; --i) { nxt2[0][i] = tree.query(A[i], N + 1).minv; tree.update(T({ i }), A[i], A[i] + 1); } for (int i = 0; i + 1 < nxt2.size(); ++i) { for (int u = 0; u < N; ++u) { int v = nxt2[i][u]; if (v < N) nxt2[i + 1][u] = nxt2[i][v]; } } while (Q--) { int P, L, R; cin >> P >> L >> R; --L; int ans = 1; for (int i = nxt2.size() - 1; ~i; --i) { if (nxt2[i][L] < R) { ans += 1 << i; L = nxt2[i][L]; } } cout << ans << endl; } return 0; }