Submission #1015130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015130		Nurislam	Gift Exchange (JOI24_ho_t4)	C++17	4 / 100	2594 ms	21140 KiB

Main

#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()){
					bool ok = 0;
					deque<pair<pair<int,int> ,pair<int,int> > > nw;
					pair<pair<int,int> ,pair<int,int> > toadd;
					auto _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";
		}
		
		
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 

• Subtask 1: 4 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 10
• Subtask 4: 0 / 31
• Subtask 5: 0 / 8
• Subtask 6: 0 / 12
• Subtask 7: 0 / 18
• Subtask 8: 0 / 12