CF1904D2 AC

pb_jiang

May 17th, 2025

365

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.58 KB | None | 0 0

raw download clone embed print report

// Problem: D2. Set To Max (Hard Version)
// Contest: Codeforces - Codeforces Round 914 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1904/D2
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
void solve()
{
ll n;
cin >> n;
vl as(n), bs(n);
for (auto &x : as)
cin >> x;
for (auto &x : bs)
cin >> x;
map<ll, vl> tg, src;
for (ll i = 0; i < n; ++i) {
if (bs[i] < as[i]) {
cout << "NO\n";
return;
}
tg[bs[i]].push_back(i);
src[as[i]].push_back(i);
}
for (auto &[k, v] : tg)
if (src.count(k) == 0) {
cout << "NO\n";
return;
}
set<ll> taken, forbid;
taken.insert(-1), taken.insert(1e9);
for (ll i = 0; i < n; ++i)
forbid.insert(i);
forbid.insert(-1), forbid.insert(1e9);
for (auto &[k, v] : tg) {
auto ids = src[k];
vl avail;
for (auto it = src.begin(); it != src.end() && it->first <= k; it = src.erase(it))
avail.insert(avail.end(), it->second.begin(), it->second.end());
for (auto x : avail)
forbid.erase(x);
dbg(k, v, ids);
dbg(taken, forbid);
for (auto i : v) {
if (as[i] == bs[i])
continue;
bool found = false;
auto it1 = lower_bound(ids.begin(), ids.end(), i);
auto it2 = taken.lower_bound(i);
auto it3 = forbid.lower_bound(i);
if (it1 != ids.end()) {
found = found || (*it2 > *it1 && *it3 > *it1);
}
if (it1 != ids.begin()) {
auto p1 = std::prev(it1);
auto p2 = std::prev(it2);
auto p3 = std::prev(it3);
found = found || (*p2 < *p1 && *p3 < *p1);
}
if (!found) {
cout << "NO\n";
return;
}
}
taken.insert(v.begin(), v.end());
}
cout << "YES\n";
}
int main(int argc, char **argv)
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll t;
cin >> t;
while (t--)
solve();
return 0;
};

Add Comment

Please, Sign In to add comment