Submission #1132817

#TimeUsernameProblemLanguageResultExecution timeMemory
1132817crafticatGift Exchange (JOI24_ho_t4)C++20
50 / 100
2594 ms15024 KiB
#include <bits/stdc++.h>

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (int i = 0; i < n;i++)
#define FOR(i,j, n) for (int i = j; i < n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vi A(n), B(n);

    F0R(i, n) {
       cin >> A[i];
    }
    F0R(i, n) {
        cin >> B[i];
    }

    int q; cin >> q;
    F0R(j, q) {
        int x, y; cin >> x >> y; x--;

        V<pi> items;
        Tree<pi> aL, bL;
        int R = 0;

        FOR(i, x, y) {
            items.emplace_back(B[i], A[i]);
            aL.insert({A[i], R++});
            bL.insert({B[i], R++});
        }
        std::sort(items.begin(), items.end());
        std::reverse(items.begin(), items.end());

        int in = 0, out = 0;
        bool prev = true;
        bool ans = true;

        F0R(i, items.size()) {
            auto [b,a] = items[i];

            in = aL.size() - aL.order_of_key({b, -1e9}) - 1;
            out = bL.order_of_key({a, 1e9}) - 1;
            if (in + out == (items.size() - 1))
                ans = false;
        }

        cout << (ans ? "Yes" : "No") << "\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...