Submission #1057587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057587		sammyuri	Gift Exchange (JOI24_ho_t4)	C++17	20 / 100	348 ms	7004 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];
int val[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 --;
        if (i > 0 && aa[i - 1] < bb[i])
            upd(i, (*it).second);
        val[i] = (*it).second;
        // remove too small ones
        while (s.back().first >= bb[i])
            s.pop_back();
        s.push_back({bb[i], i});
    }
    // for (int i = 0; i < n; i ++)
    //     cout << query(i, i) << " ";
    // cout << endl;
    // for (int i = 0; i < n; i ++)
    //     cout << val[i] << " ";
    // cout << endl;

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

/*
10
2 5 8 10 12 14 16 17 19 20
1 4 7 6 11 13 9 3 18 15
1
2 9
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:82:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   82 |             else cout << "No" << endl; continue;
      |             ^~~~
Main.cpp:82:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   82 |             else cout << "No" << endl; continue;
      |                                        ^~~~~~~~

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