이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
const int N = 2e5+5, inf = 1e16, mod = 1e9+7;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
void solve(){
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> a(n), b(n);
for(int &i:a)cin >> i;
for(int &i:b)cin >> i;
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
multiset<pair<int,int>> crb;
vector<pair<int,int> > cra;
for(int i = l-1; i < r; i++){
cra.pb({a[i], i});
crb.insert({b[i], i});
}
bool ans = 1;
sort(all(cra));
deque<pair<pair<int,int> ,pair<int,int> > > q;
for(int i = 0; i < (r-l)+1; i++){
auto it = crb.lower_bound({cra[i].ff, inf});
//cout << cra[i].ss << ' ';
if(it == crb.end())--it;
if((*it).ff > cra[i].ff){
if(it == crb.begin()){
ans = 0;
break;
}--it;
}
bool added = 1;
if((*it).ss == cra[i].ss){
if(it == crb.begin()){
if(q.empty()){
ans = 0;
break;
}
bool ok = 0;
deque<pair<pair<int,int> ,pair<int,int> > > nw;
pair<pair<int,int> ,pair<int,int> > toadd;
pair<int,int> _B = (*it);
for(auto &[A, B]:q){
if(!ok){
auto &[av, ida] = A;
auto &[bv, idb] = B;
auto &[cva, cida] = cra[i];
auto &[cvb, cidb] = _B;
if(ida != cidb && cida != idb && av > cvb && cva > bv){
swap(B, _B);
nw.pb({A,_B});
toadd = {cra[i], B};
ok = 1;
}
}else{
nw.pb({A,B});
}
}
if(ok == 1){
nw.pb(toadd);
added = 0;
}else{
ans = 0;
break;
}
q = nw;
}
it--;
}
//cout << (*it).ss << '\n';
if(added){
q.pb({cra[i], (*it)});
}
crb.erase(it);
while(q.size() > 20)q.pop_front();
}
if(ans){
cout << "Yes\n";
}
else{
cout << "No\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |