Submission #1200361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200361		Szil	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	276 ms	5936 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500'001;

int a[MAXN], b[MAXN];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        if (q > 10) {
            cout << (a[l] >= b[r] ? "Yes\n" : "No\n");
            continue;
        }
        multiset<pair<int, int>> v;
        for (int i = l; i <= r; i++) v.insert({a[i], b[i]});
        bool ok = true;
        while (!v.empty() && ok) {
            if (v.size() == 1) {
                ok = false;
                break;
            }
            auto [x, y] = *v.rbegin();
            int curr = y;
            int len = 0;
            while (1) {
                auto it = v.lower_bound({curr, 0});
                if (it == v.end()) {
                    ok = false;
                    break;
                }
                auto [nx, ny] = *it;
                if (nx == x && ny == y) break;
                len++;
                v.erase(it);
                curr = ny;
            }
            if (len == 0) {
                ok = false;
            }
            v.erase(prev(v.end()));
        }
        cout << (ok?"Yes\n":"No\n");
    }
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    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