結果
| 問題 |
No.1768 The frog in the well knows the great ocean.
|
| コンテスト | |
| ユーザー |
 riano
|
| 提出日時 | 2021-11-26 23:19:47 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 260 ms / 3,000 ms |
| コード長 | 10,203 bytes |
| コンパイル時間 | 1,763 ms |
| コンパイル使用メモリ | 185,988 KB |
| 実行使用メモリ | 23,324 KB |
| 最終ジャッジ日時 | 2024-06-29 19:02:54 |
| 合計ジャッジ時間 | 7,049 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 27 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rrep2(i,n,k) for(int i=n-1;i>=n-k;i--)
#define vll(n,i) vector<long long>(n,i)
#define v2ll(n,m,i) vector<vector<long long>>(n,vll(m,i))
#define v3ll(n,m,k,i) vector<vector<vector<long long>>>(n,v2ll(m,k,i))
#define v4ll(n,m,k,l,i) vector<vector<vector<vector<long long>>>>(n,v3ll(m,k,l,i))
#define all(v) v.begin(),v.end()
#define chmin(k,m) k = min(k,m)
#define chmax(k,m) k = max(k,m)
#define Pr pair<ll,ll>
#define Tp tuple<int,int,int>
#define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr)
using Graph = vector<vector<int>>;
const ll mod = 998244353;
template<uint64_t mod>
struct modint{
uint64_t val;
constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){}
constexpr modint operator-() const noexcept{
return modint(*this)=mod-val;
}
constexpr modint operator+(const modint rhs) const noexcept{
return modint(*this)+=rhs;
}
constexpr modint operator-(const modint rhs) const noexcept{
return modint(*this)-=rhs;
}
constexpr modint operator*(const modint rhs) const noexcept{
return modint(*this)*=rhs;
}
constexpr modint operator/(const modint rhs) const noexcept{
return modint(*this)/=rhs;
}
constexpr modint &operator+=(const modint rhs) noexcept{
val+=rhs.val;
val-=((val>=mod)?mod:0);
return (*this);
}
constexpr modint &operator-=(const modint rhs) noexcept{
val+=((val<rhs.val)?mod:0);
val-=rhs.val;
return (*this);
}
constexpr modint &operator*=(const modint rhs) noexcept{
val=val*rhs.val%mod;
return (*this);
}
constexpr modint &operator/=(modint rhs) noexcept{
uint64_t ex=mod-2;
modint now=1;
while(ex){
now*=((ex&1)?rhs:1);
rhs*=rhs,ex>>=1;
}
return (*this)*=now;
}
modint & operator++(){
val++;
if (val == mod) val = 0;
return *this;
}
modint operator++(int){
modint<mod> res = *this;
++*this;
return res;
}
constexpr bool operator==(const modint rhs) noexcept{
return val==rhs.val;
}
constexpr bool operator!=(const modint rhs) noexcept{
return val!=rhs.val;
}
friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{
return os<<(x.val);
}
friend constexpr istream &operator>>(istream& is,modint& x) noexcept{
uint64_t t;
is>>t,x=t;
return is;
}
};
typedef modint<mod> mint;
mint pw(long long a,long long b,long long m = mod){
if(a%m==0) return mint(0);
if(b==0) return mint(1);
else if(b%2==0){
long long x = pw(a,b/2,m).val;
return mint(x*x);
}
else{
long long x = pw(a,b-1,m).val;
return mint(a*x);
}
}
mint modinv(long long a, long long m = mod) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
return mint(u);
}
#define vm(n,i) vector<mint>(n,i)
#define v2m(n,m,i) vector<vector<mint>>(n,vm(m,i))
#define v3m(n,m,k,i) vector<vector<vector<mint>>>(n,v2m(m,k,i))
#define v4m(n,m,k,l,i) vector<vector<vector<vector<mint>>>>(n,v3m(m,k,l,i))
//binary trie (dynamic segtree version)
class binary_trie {
public:
ll n; ll len;
vector<vector<int>> to;
vector<int> content;
vector<int> count;
//vector<ll> sum;
//vector<ll> lis;
vector<int> emp = {-1,-1};
binary_trie(ll k){
n = 1;
len = k;
to.push_back(emp);
content.push_back(0);
count.push_back(0);
//sum.push_back(0);
}
//0-1のvectorに変換
vector<int> convert(ll x){
vector<int> c;
for(int i=0;i<=len;i++){
c.push_back(x%2); x /= 2;
}
return c;
}
mint size(void){
return count[0];
}
//xを追加する 既に存在していたらtrue
bool insert(ll x,int cc = 1){
bool ex = true;
auto p = convert(x);
int now = 0; count[now] += cc; //sum[now] += mint(x)*cc;
for(int i=len-1;i>=0;i--){
bool found = false;
if(to[now][p[i]]!=-1){
found = true;
now = to[now][p[i]]; count[now] += cc; //sum[now] += mint(x)*cc;
}
if(found) continue;
ex = false;
to[now][p[i]] = n;
to.push_back(emp);
content.push_back(p[i]);
count.push_back(cc);
//sum.push_back(mint(x)*cc);
now = n;
n++;
}
return ex;
}
//k以下の数の個数
int count_under(int k){
insert(k,0);
auto p = convert(k);
int now = 0; int res = 0;
for(int i=len-1;i>=0;i--){
if(p[i]==1&&to[now][0]!=-1){
res += count[to[now][0]];
}
now = to[now][p[i]];
}
res += count[now];
return res;
}
int binary_src(int k){
auto p = convert(k);
int now = 0; int res = 0;
int num = 0;
for(int i=len-1;i>=0;i--){
//cout << now << endl;
if(i==0){
res += count[now];
if(num-res==k){
return num;
}
else if(num-res==k-1){
return num+1;
}
}
else if(to[now][0]==-1){
if(res+num+(1LL<<(i-1))-1>=k){
return k-res;
}
else if(to[now][1]!=-1){
now = to[now][1]; continue;
}
else{
return k-(res+count[to[now][0]]);
}
}
else{
if(res+num+(1LL<<(i-1))-1+count[to[now][0]]>=k){
now = to[now][0];
}
else{
if(to[now][1]!=-1){
res += count[to[now][0]];
num += (1LL<<(i-1));
now = to[now][1];
}
else{
return k-(res+count[to[now][0]]);
}
}
}
}
return res;
}
};
//binary indexed tree
//1-indexed
class BIT {
public:
ll n;
vector<ll> a;
BIT(ll k){
n=k; a=vector<ll>(n+1,0);
}
//a[i]にxを加算する
void add(ll i,ll x){
if(i==0) return;
for(ll k=i;k<=n;k+=(k & -k)){
a[k]+=x;
}
}
//a[i]+a[i+1]+…+a[j]を求める
ll sum(ll i,ll j){
return sum_sub(j)-sum_sub(i-1);
}
//a[0]+a[1]+…+a[i]を求める
ll sum_sub(ll i){
ll s=0;
if(i==0) return s;
for(ll k=i;k>0;k-=(k & -k)){
s+=a[k];
}
return s;
}
//a[0]+a[1]+…+a[i]>=xとなる最小のiを求める(任意のkでa[k]>=0が必要)
ll lower_bound(ll x){
if(x<=0){
//xが0以下の場合は該当するものなし→0を返す
return 0;
}else{
ll i=0;ll r=1;
//最大としてありうる区間の長さを取得する
//n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
while(r<n) r=r<<1;
//区間の長さは調べるごとに半分になる
for(int len=r;len>0;len=len>>1) {
//その区間を採用する場合
if(i+len<n && a[i+len]<x){
x-=a[i+len];
i+=len;
}
}
return i+1;
}
}
};
//main関数内で BIT seq(N);
//などと宣言し seq.add(a,b);
//のように使う
int main() {
riano_; string ans;
ll T; cin >> T;
rep(ii,T){
ll N; cin >> N; ans = "Yes";
BIT seq(N+2);
vector<vector<int>> a(N+1),b(N+1);
rep(i,N){
ll c; cin >> c; a[c].push_back(i+1);
}
rep(i,N){
ll c; cin >> c; b[c].push_back(i+1);
}
rep(i,N){
seq.add(i+1,1);
}
rep(i,N+1){
vector<Pr> ran; ran.push_back(make_pair(-2e9,-2e9));
for(ll id:a[i]){
seq.add(id,-1);
}
for(ll id:a[i]){
//解から二分探索 binary search
//分かれ目の"r"側の値を求める
ll l,r;
l = 0; r = id; //初期値の代入
while(l<r){
ll c = (l+r)/2;
//cの場合に検証
ll s = seq.sum(c,id);
if(s>0){//cが"l側"になる条件判定
l = c+1;
}
else r = c;
}
ll l2 = l;
if(l2==0) l2 = 1;
l = id; r = N+1; //初期値の代入
while(l<r){
ll c = (l+r)/2;
//cの場合に検証
ll s = seq.sum(id,c);
if(s==0){//cが"l側"になる条件判定
l = c+1;
}
else r = c;
}
ll r2 = l-1;
ran.push_back(make_pair(l2,r2));
// cout << id << endl;
// cout << l2 << " " << r2 << endl;
}
sort(all(ran));
for(ll id:b[i]){
Pr p = make_pair(id,2e9);
ll k = lower_bound(all(ran),p)-ran.begin()-1;
ll l2 = ran[k].first; ll r2 = ran[k].second;
if(id<l2||id>r2){
ans = "No"; break;
}
seq.add(id,20);
}
if(ans=="No") break;
}
cout << ans << "\n";
}
}