Submission #1095309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095309		Triseedot	Gift Exchange (JOI24_ho_t4)	C++17	100 / 100	700 ms	91616 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 FenwickTree {
    vector<ll> tree;
    int n;

    void increase(int i, int val) {
        for (i = i + 1; i <= n; i += low_bit(i)) {
            tree[i] += val;
        }
    }

    void build(const vector<int>& a) {
        n = len(a);
        tree.assign(n + 1, 0);
        for (int i = 0; i < n; i++) {
            increase(i, a[i]);
        }
    }

    ll get(int r) {
        ll res = 0;
        for (int i = r; i > 0; i -= low_bit(i)) {
            res += tree[i];
        }
        return res;
    }

    ll get(int l, int r) {
        return get(r) - get(l);
    }

    int lower_bound(ll val) {
        int l = 0;
        for (int i = log2_floor(n) + 1; i >= 0; i--) {
            int r = l + (1 << i);
            if (r <= n && val > tree[r]) {
                val -= tree[r];
                l = r;
            }
        }
        return l;
    }
};

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

    struct query {
        int l, r, i;
    };
    vector<bool> ans(m);
    vector<vector<query>> q(n);
    for (int i = 0; i < m; i++) {
        query qi;
        cin >> qi.l >> qi.r;
        qi.l--, qi.r--;
        qi.i = i;
        q[qi.r].push_back(qi);
    }

    FenwickTree tree;
    tree.build(vector(n + 1, 0));
    auto add = [&] (int l, int r) {
        tree.increase(l, 1);
        tree.increase(r + 1, -1);
    };
    auto ers = [&] (int l, int r) {
        tree.increase(l, -1);
        tree.increase(r + 1, 1);
    };
    auto get = [&] (int i) {
        return tree.get(i + 1);
    };
    vector<vector<pair<int, int>>> to_ers(n);
    for (int i = 0; i < n; i++) {
        for (auto [l_, r_] : to_ers[i]) {
            ers(l_, r_);
        }
        int l_, r_ = i;
        if (!l[i].has_value()) l_ = 0;
        else l_ = *l[i] + 1;
        add(l_, r_);
        if (r[i].has_value()) to_ers[*r[i]].emplace_back(l_, r_);
        for (auto qi : q[i]) {
            if (get(qi.l) == 0) ans[qi.i] = true;
            else ans[qi.i] = false;
        }
    }

    for (int i = 0; i < m; i++) {
        if (ans[i]) cout << "Yes\n";
        else cout << "No\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: 8 / 8
• Subtask 6: 12 / 12
• Subtask 7: 18 / 18
• Subtask 8: 12 / 12