Submission #1107999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107999		_callmelucian	Gift Exchange (JOI24_ho_t4)	C++14	100 / 100	1247 ms	98344 KiB

Main

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct lazyIT {
    vector<int> tr, lazy;
    lazyIT (int sz) : tr(4 * sz), lazy(4 * sz) {}

    void apply (int k, int val) {
        tr[k] = max(tr[k], val), lazy[k] = max(lazy[k], val);
    }

    void pushDown (int k) {
        if (lazy[k])
            apply(2 * k, lazy[k]), apply(2 * k + 1, lazy[k]), lazy[k] = 0;
    }

    void update (int a, int b, int val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b)
            return apply(k, val), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        update(a, b, val, 2 * k, l, mid);
        update(a, b, val, 2 * k + 1, mid + 1, r);
        tr[k] = max(tr[2 * k], tr[2 * k + 1]);
    }

    int query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return tr[k];
        pushDown(k);
        int mid = (l + r) >> 1;
        return max(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
    }
};

struct IT {
    vector<int> tr;
    IT (int sz) : tr(4 * sz) {}

    void update (int pos, int val, int k, int l, int r) {
        if (pos < l || r < pos) return;
        if (l == r) return tr[k] = val, void();
        int mid = (l + r) >> 1;
        update(pos, val, 2 * k, l, mid);
        update(pos, val, 2 * k + 1, mid + 1, r);
        tr[k] = min(tr[2 * k], tr[2 * k + 1]);
    }

    int query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return INT_MAX;
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        return min(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
    }
};

vector<int> lastIntersect (const vector<pii> &vec, int n) {
    vector<int> ans(n + 1);
    lazyIT tree(2 * n);

    for (int i = 1; i <= n; i++) {
        int a, b; tie(a, b) = vec[i];
        ans[i] = tree.query(a, b, 1, 1, 2 * n);
        tree.update(a, b, i, 1, 1, 2 * n);
    }
    return ans;
}

template <typename T>
vector<T> rev (const vector<T> &vec, int n) {
    vector<T> ans(n + 1);
    for (int i = 1; i <= n; i++) ans[n - i + 1] = vec[i];
    return ans;
}

const int mn = 1e6 + 6;
vector<int> sweep[mn];
vector<pii> qry[mn];
bool ans[mn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    // read input
    int n; cin >> n;
    vector<pii> vec(n + 1);

    for (int i = 1; i <= n; i++) cin >> vec[i].second;
    for (int i = 1; i <= n; i++) cin >> vec[i].first;

    // process queries
    vector<int> toLeft = lastIntersect(vec, n);
    vector<int> toRight = rev(lastIntersect(rev(vec, n), n), n);

    IT tree(n);
    for (int i = 1; i <= n; i++) {
        tree.update(i, toLeft[i], 1, 1, n);
        sweep[n - toRight[i] + 1].push_back(i);
    }

    // read query
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        qry[r].emplace_back(l, i);
    }

    // process queries
    for (int i = 1; i <= n; i++) {
        for (int u : sweep[i]) tree.update(u, u, 1, 1, n);
        for (pii item : qry[i]) {
            int l, idx; tie(l, idx) = item;
            ans[idx] = tree.query(l, i, 1, 1, n) >= l;
        }
    }

    // answer queries
    for (int i = 0; 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