結果

問題 No.1768 The frog in the well knows the great ocean.
ユーザー kwm_tkwm_t
提出日時 2023-12-10 15:31:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 155 ms / 3,000 ms
コード長 4,943 bytes
コンパイル時間 2,442 ms
コンパイル使用メモリ 211,372 KB
実行使用メモリ 25,504 KB
最終ジャッジ日時 2023-12-10 15:31:49
合計ジャッジ時間 6,367 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 5 ms
6,676 KB
testcase_02 AC 6 ms
6,676 KB
testcase_03 AC 5 ms
6,676 KB
testcase_04 AC 6 ms
6,676 KB
testcase_05 AC 6 ms
6,676 KB
testcase_06 AC 114 ms
9,784 KB
testcase_07 AC 116 ms
13,624 KB
testcase_08 AC 98 ms
11,884 KB
testcase_09 AC 99 ms
9,492 KB
testcase_10 AC 107 ms
14,244 KB
testcase_11 AC 129 ms
14,584 KB
testcase_12 AC 121 ms
14,588 KB
testcase_13 AC 115 ms
14,584 KB
testcase_14 AC 113 ms
14,580 KB
testcase_15 AC 136 ms
14,576 KB
testcase_16 AC 155 ms
24,924 KB
testcase_17 AC 141 ms
24,932 KB
testcase_18 AC 143 ms
24,912 KB
testcase_19 AC 133 ms
24,928 KB
testcase_20 AC 146 ms
24,916 KB
testcase_21 AC 2 ms
6,676 KB
testcase_22 AC 2 ms
6,676 KB
testcase_23 AC 3 ms
6,676 KB
testcase_24 AC 115 ms
6,676 KB
testcase_25 AC 100 ms
25,504 KB
testcase_26 AC 82 ms
25,500 KB
testcase_27 AC 2 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1
#ifdef _MSC_VER
#include <intrin.h>
#include<cassert>
#endif
namespace atcoder {
	namespace internal {
		int ceil_pow2(int n) {
			int x = 0;
			while ((1U << x) < (unsigned int)(n)) x++;
			return x;
		}
		int bsf(unsigned int n) {
#ifdef _MSC_VER
			unsigned long index;
			_BitScanForward(&index, n);
			return index;
#else
			return __builtin_ctz(n);
#endif
		}
	}
}
#endif
#ifndef ATCODER_SEGTREE_HPP
#define ATCODER_SEGTREE_HPP 1
#include <algorithm>
#include <cassert>
#include <vector>
namespace atcoder {
	template <class S, S(*op)(S, S), S(*e)()> struct segtree {
	public:
		segtree() : segtree(0) {}
		segtree(int n) : segtree(std::vector<S>(n, e())) {}
		segtree(const std::vector<S>& v) : _n(int(v.size())) {
			log = internal::ceil_pow2(_n);
			size = 1 << log;
			d = std::vector<S>(2 * size, e());
			for (int i = 0; i < _n; i++) d[size + i] = v[i];
			for (int i = size - 1; i >= 1; i--) {
				update(i);
			}
		}
		void set(int p, S x) {
			assert(0 <= p && p < _n);
			p += size;
			d[p] = x;
			for (int i = 1; i <= log; i++) update(p >> i);
		}
		S get(int p) {
			assert(0 <= p && p < _n);
			return d[p + size];
		}
		S prod(int l, int r) {
			assert(0 <= l && l <= r && r <= _n);
			S sml = e(), smr = e();
			l += size;
			r += size;
			while (l < r) {
				if (l & 1) sml = op(sml, d[l++]);
				if (r & 1) smr = op(d[--r], smr);
				l >>= 1;
				r >>= 1;
			}
			return op(sml, smr);
		}
		S all_prod() { return d[1]; }
		template <bool(*f)(S)> int max_right(int l) {
			return max_right(l, [](S x) { return f(x); });
		}
		template <class F> int max_right(int l, F f) {
			assert(0 <= l && l <= _n);
			assert(f(e()));
			if (l == _n) return _n;
			l += size;
			S sm = e();
			do {
				while (l % 2 == 0) l >>= 1;
				if (!f(op(sm, d[l]))) {
					while (l < size) {
						l = (2 * l);
						if (f(op(sm, d[l]))) {
							sm = op(sm, d[l]);
							l++;
						}
					}
					return l - size;
				}
				sm = op(sm, d[l]);
				l++;
			} while ((l & -l) != l);
			return _n;
		}
		template <bool(*f)(S)> int min_left(int r) {
			return min_left(r, [](S x) { return f(x); });
		}
		template <class F> int min_left(int r, F f) {
			assert(0 <= r && r <= _n);
			assert(f(e()));
			if (r == 0) return 0;
			r += size;
			S sm = e();
			do {
				r--;
				while (r > 1 && (r % 2)) r >>= 1;
				if (!f(op(d[r], sm))) {
					while (r < size) {
						r = (2 * r + 1);
						if (f(op(d[r], sm))) {
							sm = op(d[r], sm);
							r--;
						}
					}
					return r + 1 - size;
				}
				sm = op(d[r], sm);
			} while ((r & -r) != r);
			return 0;
		}
	private:
		int _n, size, log;
		std::vector<S> d;
		void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
	};
}
#endif
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
//using mint = modint998244353;
//const int mod = 998244353;
//using mint = modint1000000007;
//const int mod = 1000000007;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
int op(int a, int b) { return a + b; }
int e() { return 0; }
int op2(int a, int b) { return max(a, b); }
int e2() { return -1; }
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t; cin >> t;
	while (t--) {
		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]--;
		vector<vector<int>>pos(n);
		vector<vector<int>>v(n);
		rep(i, n) {
			pos[a[i]].push_back(i);
			v[b[i]].push_back(i);
		}
		bool chk = true;
		segtree<int, op, e>seg(n);
		segtree<int, op2, e2>seg2(a);
		rep(i, n) {
			rep(j, v[i].size()) {
				bool subchk = false;
				//以下の数
				int cnt0 = upper_bound(all(pos[i]), v[i][j]) - pos[i].begin();
				if (0 != cnt0) {
					int idx = pos[i][cnt0 - 1];
					auto get = seg.prod(idx, v[i][j] + 1);
					auto mx = seg2.prod(idx, v[i][j] + 1);
					//cout << get << endl;
					if (mx == i && !get)subchk = true;
				}
				//以上の数
				int cnt1 = pos[i].end() - lower_bound(all(pos[i]), v[i][j]);
				if (0 != cnt1) {
					int idx = pos[i][pos[i].size() - cnt1];
					auto get = seg.prod(v[i][j], idx + 1);
					auto mx = seg2.prod(v[i][j], idx + 1);
					//cout << get << endl;
					if (mx == i && !get)subchk = true;
				}
				if (!subchk)chk = false;
			}
			if (!chk)break;
			rep(j, v[i].size()) seg.set(v[i][j], 1);
		}
		if (chk)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}
0