Submission #1206031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206031		ofoz	Gift Exchange (JOI24_ho_t4)	C++20	9 / 100	2594 ms	1864 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pi pair<int, int>

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    vector<int> left(n, INT32_MIN), right(n, INT32_MAX);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if ((a[i] < b[j] ) || b[i] > a[j]) continue;
            if (j < i) left[i] = max(left[i], j);
            else right[i] = min(right[i], j);
        }
    }
    int q;
    cin >> q;
    vector<vector<pi>> queryR(n);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        queryR[r].push_back({l, i});
    }
    vector<bool> res(q, false);
    vi c(n);
    for (int i = 0; i < n; i++) c[i] = left[i];
    for (int r = 0; r < n; r++) {
        for (int i = 0; i < n; i++) {
            if (right[i] == r) c[i] = INT32_MAX;
        }
        for (pi p : queryR[r]) {
            int l, i;
            tie(l, i) = p;
            int mn = *min_element(c.begin() + l, c.begin() + r + 1);
            cerr << mn << endl;
            res[i] = mn >= l;
        }
    }
    for (bool b : res) {
        cout << (b ? "Yes" : "No") << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 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