Submission #1132817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132817		crafticat	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	2594 ms	15024 KiB

Main

#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;
}

• 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