Submission #1183530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183530		TudorMa	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	884 ms	103076 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fi first
#define sc second
#define pb push_back

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
template<typename type>
using ordered_set = tree<type, null_type, less<type>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5e5 + 5, Q = 2e5 + 5, mod = 1e9 + 7, inf = 2e9;
const int dl[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
const int ddl[] = {-1, -1, -1, 0, 1, 1, 1, 0}, ddc[] = {-1, 0, 1, 1, 1, 0, -1, -1};

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int rng(int lo = 1, int hi = INT_MAX) {
    uniform_int_distribution<int> rnd(lo, hi);
    return rnd(gen);
}

struct mint {
    int val;
    mint(int32_t x = 0) {
        val = x % mod;
    }
    mint(long long x) {
        val = x % mod;
    }
    mint operator+(mint x) {
        return val + x.val;
    }
    mint operator-(mint x) {
        return val - x.val + mod;
    }
    mint operator*(mint x) {
        return 1LL * val * x.val;
    }
    void operator+=(mint x) {
        val = (*this + x).val;
    }
    void operator-=(mint x) {
        val = (*this - x).val;
    }
    void operator*=(mint x) {
        val = (*this * x).val;
    }
    friend auto operator>>(istream& in, mint &x) -> istream& {
        in >> x.val;
        x.val %= mod;
        return in;
    }
    friend auto operator<<(ostream& out, mint const &x) -> ostream& {
        out << x.val;
        return out;
    }
};

int n, q, a[N], b[N], lb[N], rb[N], lg2[N], l[Q], r[Q], ans[Q];
vector<pii> add[N], rmv[N];
vector<int> qrs[N];

struct segtree {
    int tree[8*N], lazy[8*N];

    void propag(int nod) {
        tree[nod<<1] = lazy[nod];
        tree[nod<<1|1] = lazy[nod];
        lazy[nod<<1] = lazy[nod];
        lazy[nod<<1|1] = lazy[nod];
        lazy[nod] = 0;
    }   
    void update(int nod, int st, int dr, int l, int r, int x) {
        if(lazy[nod] && st != dr)
            propag(nod);
        if(l <= st && dr <= r) {
            tree[nod] = x;
            lazy[nod] = x;
        }
        else {
            int mid = (st + dr) / 2;
            if(l <= mid)
                update(nod<<1, st, mid, l, r, x);
            if(mid < r)
                update(nod<<1|1, mid+1, dr, l, r, x);
            
            tree[nod] = max(tree[nod<<1], tree[nod<<1|1]);
        }
    }
    int query(int nod, int st, int dr, int l, int r) {
        if(lazy[nod] && st != dr)
            propag(nod);
        if(l <= st && dr <= r)
            return tree[nod];
        else {
            int mid = (st + dr) / 2;
            int s1 = -inf, s2 = -inf;
            if(l <= mid)
                s1 = query(nod<<1, st, mid, l, r);
            if(mid < r)
                s2 = query(nod<<1|1, mid+1, dr, l, r);
            
            return max(s1, s2);
        }
    }
    void update(int l, int r, int x) {
        update(1, 1, 2*n, l, r, x);
    }
    int query(int l, int r) {
        return query(1, 1, 2*n, l, r);
    }
} aint;
struct fenwick {
    int t[N];

    inline int lsb(int x) {
        return x & -x;
    }
    void update(int p, int x) {
        if(!p)
            return;
        while(p <= n) {
            t[p] += x;
            p += lsb(p);
        }
    }
    int pref(int p) {
        int ans = 0;
        while(p) {
            ans += t[p];
            p -= lsb(p);
        }

        return ans;
    }
    int query(int l, int r) {
        return pref(r) - pref(l-1);
    }
} aib;

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);

    lg2[1] = 0;
    for(int i=2; i<N; i++)
        lg2[i] = lg2[i>>1] + 1;

    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    for(int i=1; i<=n; i++)
        cin >> b[i];
    cin >> q;
    for(int i=1; i<=q; i++) {
        cin >> l[i] >> r[i];
        qrs[l[i]].pb(i);
    }

    for(int i=1; i<=n; i++) {
        lb[i] = aint.query(b[i], a[i]);
        aint.update(b[i], a[i], i);
    }
    aint.update(1, 2*n, -n-1);
    for(int i=n; i>=1; i--) {
        rb[i] = -aint.query(b[i], a[i]);
        aint.update(b[i], a[i], -i);
    }
    for(int i=1; i<=n; i++) {
        add[lb[i]+1].pb({i, rb[i]});
        rmv[i].pb({i, rb[i]});
    }

    for(int i=1; i<=n; i++) {
        for(auto &[x, y] : add[i]) {
            aib.update(x, 1);
            aib.update(y, -1);
        }
        for(auto qr : qrs[i])
            ans[qr] = !aib.query(i, r[qr]);
        for(auto &[x, y] : rmv[i]) {
            aib.update(x, -1);
            aib.update(y, 1);
        }
    }

    for(int i=1; i<=q; i++)
        cout << (ans[i] ? "Yes" : "No") << '\n';
    return 0;
}

• 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