Submission #1057536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057536		sammyuri	Gift Exchange (JOI24_ho_t4)	C++17	50 / 100	2598 ms	11900 KiB

Main

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

/*
one strategy:
sort by a_i
go from left to right and assign to the rightmost one which
has b_i >= current a_i (and is not i itself)
is this guaranteed to work?
*/

struct state {
    int value; int index;
    bool is_b;
    state (int _p, int _i, int _b) {
        value = _p, index = _i, is_b = _b;
    }
};
bool operator < (state a, state b) {
    if (a.value != b.value)
        return a.value < b.value;
    if (a.is_b != b.is_b)
        return a.is_b;
    return a.index < b.index;
}

bool solve(vector<int> aa, vector<int> bb) {
    int n = aa.size();
    vector<pair<int, int>> k;
    for (int i = 0; i < n; i ++)
        k.push_back({aa[i], bb[i]});
    sort(k.begin(), k.end());
    vector<state> updates;
    for (int i = 0; i < n; i ++) {
        updates.push_back(state(k[i].first, i, false));
        updates.push_back(state(k[i].second, i, true));
    }
    sort(updates.begin(), updates.end());
    set<int> active;
    for (int i = 0; i < updates.size(); i ++) {
        if (updates[i].is_b) {
            active.insert(updates[i].index);
        } else {
            if (!active.size())
                return false;
            auto it = active.rbegin();
            if (*it == updates[i].index) {
                if (active.size() == 1)
                    return false;
                it ++;
            }
            active.erase(*it);
        }
    }
    return true;
}

int main() {
    int n; cin >> n;
    vector<int> aa(n), bb(n);
    for (auto &a : aa) cin >> a;
    for (auto &a : bb) cin >> a;
    int q; cin >> q;
    while (q --) {
        int l, r; cin >> l >> r;
        l --; r --;
        vector<int> a2, b2;
        for (int i = l; i <= r; i ++)
            a2.push_back(aa[i]), b2.push_back(bb[i]);
        if (solve(a2, b2))
            cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool solve(std::vector<int>, std::vector<int>)':
Main.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < updates.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~~~

• 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