Submission #1057584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057584		sammyuri	Gift Exchange (JOI24_ho_t4)	C++17	0 / 100	339 ms	5720 KiB

Main

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

/*
for each index, calculate val[i],
the minimum index j > i such that they intersect
note that it is valid iff for all l, l + 1, .. , r - 1
val[i] <= r
so use a max segtree?
*/

const int MAXN = (1 << 17);
int tree[2 * MAXN];
void init() {
    for (int i = 0; i < MAXN * 2; i ++)
        tree[i] = -1;
}
void upd(int index, int value) {
    index += MAXN;
    tree[index] = value;
    index /= 2;
    while (index) {
        tree[index] = max(tree[2 * index], tree[2 * index + 1]);
        index /= 2;
    }
}
int query(int left, int right, int index, int maxl, int maxr) {
    if (left == maxl && right == maxr)
        return tree[index];
    int ans = -1;
    int mid = (maxl + maxr) / 2;
    if (left <= mid) {
        ans = max(ans, query(left, min(mid, right), 2 * index, maxl, mid));
    }
    if (right >= mid + 1) {
        ans = max(ans, query(max(mid + 1, left), right, 2 * index + 1, mid + 1, maxr));
    }
    return ans;
}
int query(int l, int r) {return query(l, r, 1, 0, MAXN - 1);}


int main() {
    int n; cin >> n;
    init();
    vector<int> aa(n), bb(n);
    for (auto &a : aa) cin >> a;
    for (auto &a : bb) cin >> a;
    // find initial values
    vector<pair<int, int>> s;
    s.push_back({0, n});
    for (int i = n - 1; i >= 0; i --) {
        // find next in line
        auto it = lower_bound(s.begin(), s.end(), (pair<int, int>){aa[i], 1e9});
        it --;
        upd(i, (*it).second);
        // remove too small ones
        while (s.back().first >= bb[i])
            s.pop_back();
        s.push_back({bb[i], i});
    }

    int q; cin >> q;
    while (q --) {
        int l, r; cin >> l >> r;
        l --; r --;
        if (l == r) {
            cout << "No" << endl; continue;
        }
        int xx = query(l, r - 1);
        if (xx <= r)
            cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 10
• Subtask 4: 0 / 31
• Subtask 5: 0 / 8
• Subtask 6: 0 / 12
• Subtask 7: 0 / 18
• Subtask 8: 0 / 12