結果
問題 | No.1768 The frog in the well knows the great ocean. |
ユーザー |
|
提出日時 | 2021-10-23 20:13:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,956 bytes |
コンパイル時間 | 3,576 ms |
コンパイル使用メモリ | 211,348 KB |
最終ジャッジ日時 | 2025-01-25 04:59:20 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 WA * 3 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; } template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; } template<class Op> class SparseTable { using T = typename Op::T; vector<vector<T>> dat; vector<int> len; int n, log; public: SparseTable(const vector<T>& a) : n(a.size()), log(log2(n)) { dat = vector<vector<T>>(log + 1, vector<T>(n)); len.resize(n + 1); rep(i, n)dat[0][i] = a[i]; rep(j, log)rep(i, n - (1 << j)) { dat[j + 1][i] = Op::comp(dat[j][i], dat[j][i + (1 << j)]); } for (int i = 2; i <= n; ++i)len[i] = len[i >> 1] + 1; } T value(int l, int r) { int k = len[r - l]; return Op::comp(dat[k][l], dat[k][r - (1 << k)]); } }; template<class Type> struct node { using T = Type; inline static T comp(T x, T y) { return max(x, y); } }; void solve() { int n; cin >> n; vector<int> a(n), b(n); rep(i, n) { cin >> a[i]; --a[i]; } rep(i, n) { cin >> b[i]; --b[i]; } set<int> sa, sb; rep(i, n)sa.insert(i); vector<vector<pair<int, int>>> p(n); rep(i, n)p[a[i]].emplace_back(i, true); rep(i, n)p[b[i]].emplace_back(i, false); SparseTable<node<int>> sp(a); for (auto& val : p) { for (auto [i, f] : val)if (f)sa.erase(i); for (auto [i, f] : val) { if (f)continue; int l = -1, r = n; for (auto it = sa.lower_bound(i);;) { if (it != sa.begin())chmax(l, *prev(it)); if (it != sa.end())chmin(r, *it); break; } for (auto it = sb.lower_bound(i);;) { if (it != sb.begin())chmax(l, *prev(it)); if (it != sb.end())chmin(r, *it); break; } ++l, --r; if (l > r || sp.value(l, r + 1) != b[i]) { cout << "No\n"; return; } } for (auto [i, f] : val)if (!f)sb.insert(i); } cout << "Yes\n"; } int main() { int t; cin >> t; while (t--)solve(); return 0; }