結果
問題 | No.1768 The frog in the well knows the great ocean. |
ユーザー | KKT89 |
提出日時 | 2023-12-10 16:18:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 127 ms / 3,000 ms |
コード長 | 2,869 bytes |
コンパイル時間 | 2,944 ms |
コンパイル使用メモリ | 226,648 KB |
実行使用メモリ | 18,220 KB |
最終ジャッジ日時 | 2023-12-10 16:18:10 |
合計ジャッジ時間 | 6,549 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 5 ms
6,548 KB |
testcase_02 | AC | 5 ms
6,548 KB |
testcase_03 | AC | 5 ms
6,548 KB |
testcase_04 | AC | 6 ms
6,548 KB |
testcase_05 | AC | 5 ms
6,548 KB |
testcase_06 | AC | 98 ms
8,304 KB |
testcase_07 | AC | 107 ms
10,088 KB |
testcase_08 | AC | 93 ms
8,832 KB |
testcase_09 | AC | 94 ms
7,604 KB |
testcase_10 | AC | 100 ms
10,572 KB |
testcase_11 | AC | 112 ms
10,904 KB |
testcase_12 | AC | 110 ms
10,912 KB |
testcase_13 | AC | 108 ms
10,992 KB |
testcase_14 | AC | 98 ms
10,936 KB |
testcase_15 | AC | 104 ms
10,780 KB |
testcase_16 | AC | 125 ms
18,220 KB |
testcase_17 | AC | 127 ms
18,220 KB |
testcase_18 | AC | 124 ms
18,220 KB |
testcase_19 | AC | 105 ms
18,220 KB |
testcase_20 | AC | 113 ms
18,220 KB |
testcase_21 | AC | 2 ms
6,548 KB |
testcase_22 | AC | 2 ms
6,548 KB |
testcase_23 | AC | 2 ms
6,548 KB |
testcase_24 | AC | 40 ms
6,548 KB |
testcase_25 | AC | 95 ms
18,092 KB |
testcase_26 | AC | 66 ms
18,092 KB |
testcase_27 | AC | 2 ms
6,548 KB |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef unsigned long long int ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } inline double time() { return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9; } template <class S, S (*op)(S, S), S (*e)()> struct segtree { int n; vector<S> tree; segtree() : segtree(0) {} segtree(int n) : n(n), tree(vector<S>(n<<1, e())) {} // 未verify(え?) segtree(const vector<S>& v) : n((int)v.size()) { tree.resize(n*2); for (int i = 0; i < n; ++i) { tree[n+i] = v[i]; } for (int i = n - 1; i >= 1; --i) { update(i); } } void update(int k) { tree[k] = op(tree[k<<1|0], tree[k<<1|1]); } S operator[](int i) {return tree[i+n]; } void set(int i, S x) { i += n; tree[i] = x; while(i >>= 1) { update(i); } } // [l,r) S query(int l, int r) { S sml = e(), smr = e(); for(l += n, r += n; l < r; l >>= 1, r >>= 1){ if(l & 1) sml = op(sml, tree[l++]); if(r & 1) smr = op(tree[--r], smr); } return op(sml,smr); } }; using S = int; S opmin(S a, S b) { return min(a, b); } S opmax(S a, S b) { return max(a, b); } S emin() { return 1e9; } S emax() { return -1; } bool slv() { int n; cin >> n; vector<int> a(n),b(n); segtree<S,opmax,emax> seg_a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; a[i] -= 1; seg_a.set(i, a[i]); } segtree<S,opmin,emin> seg_b(n); for (int i = 0; i < n; ++i) { cin >> b[i]; b[i] -= 1; seg_b.set(i, b[i]); } vector<pair<int,int>> v(n); vector<vector<int>> pos(n); for (int i = 0; i < n; ++i) { if (a[i] > b[i]) return false; v[i] = {a[i], i}; pos[a[i]].push_back(i); } sort(v.begin(), v.end()); for (int i = 0; i < n; ++i) { int j = v[i].second; if (b[j] == a[j]) continue; auto it = lower_bound(pos[b[j]].begin(), pos[b[j]].end(), j); bool ok = false; if (it != pos[b[j]].end()) { int r = *it; if (seg_a.query(j, r) <= b[j] and seg_b.query(j, r) >= b[j]) ok = true; } if (it != pos[b[j]].begin()) { it--; int l = *it; if (seg_a.query(l, j) <= b[j] and seg_b.query(l, j) >= b[j]) ok = true; } if (!ok) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; while (q--) { if (slv()) cout << "Yes" << "\n"; else cout << "No" << "\n"; } }