結果
問題 | No.1768 The frog in the well knows the great ocean. |
ユーザー |
|
提出日時 | 2023-12-10 16:18:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 135 ms / 3,000 ms |
コード長 | 2,869 bytes |
コンパイル時間 | 3,190 ms |
コンパイル使用メモリ | 225,548 KB |
最終ジャッジ日時 | 2025-02-18 10:03:58 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 |
ソースコード
#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";}}