Submission #1095300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095300		Triseedot	Gift Exchange (JOI24_ho_t4)	C++17	50 / 100	2539 ms	13180 KiB

Main

// In honor of El Psy Congroo

//#define _GLIBCXX_DEBUG

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

// variables
using ld = long double;
using ll = long long;
using ull = unsigned long long;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
// bitwise operations
#define cnt_bit(n) __builtin_popcountll(n)
#define low_bit(n) ((n) & (-(n)))
#define bit(n, i) (((n) >> (i)) & 1)
#define set_bit(n, i) ((n) | (1ll << (i)))
#define reset_bit(n, i) ((n) & ~(1ll << (i)))
#define flip_bit(n, i) ((n) ^ (1ll << (i)))
// math
#define sqr(n) ((n) * (n))
int log2_floor(ull n) {
    return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1;
}
// vector
#define len(x) (int) x.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for(auto& el : v) { 
        is >> el;
    }
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < len(v); i++) {
        if (i) os << ' ';
        os << v[i];
    }
    return os;
}
template<class... Args>
auto create(size_t n, Args&&... args) {
    if constexpr(sizeof...(args) == 1) {
        return vector(n, args...);
    }
    else {
        return vector(n, create(args...));
    }
}
template<typename T>
void remove_dups(vector<T>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}
// random
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

//////solution start//////

struct DSU {
    int n;
    vector<int> p;

    void build(int N) {
        n = N;
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int get(int i) {
        if (p[i] == i) return i;
        return p[i] = get(p[i]);
    }

    bool unite(int i, int j) {
        i = get(i);
        j = get(j);
        if (i == j) return false;
        p[i] = j;
        return true;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    cin >> a >> b;
    for (int i = 0; i < n; i++) {
        a[i]--, b[i]--;
    }
    int m;
    cin >> m;
    vector<pair<int, int>> q(m);
    for (int i = 0; i < m; i++) {
        cin >> q[i].first >> q[i].second;
        q[i].first--, q[i].second--;
    }

    vector<optional<int>> l(n), r(n);
    set<pair<int, int>> curr;
    for (int i = 0; i < n; i++) {
        while (true) {
            auto it = curr.lower_bound({b[i], -1});
            if (it == curr.end() || it->first > a[i]) break;
            int j = it->second;
            if (!r[j].has_value() || r[j] > i) r[j] = i;
            if (!l[i].has_value() || l[i] < j) l[i] = j;
            curr.erase(it);
        }
        curr.insert({a[i], i});
    }
    curr.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (true) {
            auto it = curr.lower_bound({b[i], -1});
            if (it == curr.end() || it->first > a[i]) break;
            int j = it->second;
            if (!r[i].has_value() || r[i] > j) r[i] = j;
            if (!l[j].has_value() || l[j] < i) l[j] = i;
            curr.erase(it);
        }
        curr.insert({a[i], i});
    }

    for (auto [i, j] : q) {
        [&] () {
            for (int k = i; k <= j; k++) {
                if ((!l[k].has_value() || l[k] < i) && (!r[k].has_value() || r[k] > j)) {
                    cout << "No\n";
                    return;
                }
            }
            cout << "Yes\n";
        } ();
    }
}

//////solution end//////
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int tt = 1;
    //cin >> tt;
    for (int i = 1; i <= tt; i++) {
        solve();
    }
}

• 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