Submission #1162573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162573		akacool445k	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	2594 ms	6988 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
#define pint pair<int, int>
#define vint vector<pair<int, int>>
const int mod = 1e9 + 7;
const int shrek = 5e5 + 5;
const int say = INT_MAX / 2;
const int gex = INT_MIN / 2;
const long long oo = 1e18;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	cout.tie(0);
	int n; cin >> n;
	pair<int, int> a[n];
	for(int i = 0; i < n; i++) {
		cin >> a[i].ff;
	}
	for(int i = 0; i < n; i++) {
		cin >> a[i].ss;
	}
	int q; cin >> q;
	while(q--) {
		int l, r; cin >> l >> r;
		l--;
		r--;
		vector<pair<int, int>> b, c;
		for(int i = l; i <= r; i++) {
			c.pb({a[i].ff, i});
			b.pb({a[i].ss, i});
		}
		sort(b.begin(), b.end());
		sort(c.begin(), c.end());
		// cout << b.size() << ' ' << c.size() << '\n';
		// for(auto x : b) {
		// 	cout << x.ff << ' ' << x.ss << '\n';
		// }
		// cout << '\n';
		// for(auto x : c) {
		// 	cout << x.ff << ' ' << x.ss << '\n';
		// }
		// cout << '\n';
		int cnt = r - l + 1;
		bool gay = 1;
		for(int i = 0; i < cnt; i++) {
			if(b[i].ss != c[i].ss) {
				continue;
			}
			if(i > 0 && c[i - 1].ff > b[i].ff) {
				// swap(c[i - 1], c[i]);
				swap(b[i - 1], b[i]);
			} else if(i < cnt - 1 && c[i].ff > b[i + 1].ff) {
				// swap(c[i + 1], c[i]);
				swap(b[i + 1], b[i]);
			} else {
				gay = 0;
			}
		}
		// for(auto x : b) {
		// 	cout << x.ff << ' ' << x.ss << '\n';
		// }
		// cout << '\n';
		// for(auto x : c) {
		// 	cout << x.ff << ' ' << x.ss << '\n';
		// }
		// cout << '\n';
		for(int i = 0; i < cnt; i++) {
			if(b[i] > c[i]) {
				gay = 0;
			}
		}
		if(gay) {
			cout << "Yes" << '\n';
		} else {
			cout << "No" << '\n';
		}

	}
    return 0;
}

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