Submission #1244059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244059		sula2	Jail (JOI22_jail)	C++20	0 / 100	0 ms	328 KiB

jail

#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;

struct segtree {
    vector<int> tree;
    int offset = 1;

    segtree(int n) {
        while (offset < n) offset *= 2;
        tree.resize(offset*2, 1e9);
    }

    void update(int i, int x) {
        tree[i += offset] = x;
        while (i >>= 1) tree[i] = min(tree[i*2], tree[i*2 + 1]);
    }

    int query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (qr < l || r < ql) return 1e9;
        int mid = (l+r)/2;
        return min(
                query(2*v, l, mid, ql, qr),
                query(2*v+1, mid+1, r, ql, qr)
                );
    }

    int query(int l, int r) {
        return query(1, 0, offset - 1, l, r);
    }
};

void solve() {
    int n,m; cin >> n;
    for (int i = 0, a, b; i < n-1; cin >> a >> b, i++);
    cin >> m;
    int L[m], R[m];
    segtree s(n);
    for (int i = 0; i < m; i++) {
        cin >> L[i] >> R[i];
        L[i]--, R[i]--;
        if (L[i] < R[i]) {
            s.update(R[i], L[i]);
        }
    }
    for (int i = 0; i < m; i++) {
        if (L[i] > R[i]) {
            swap(L[i], R[i]);
            int mn = s.query(L[i], R[i]);
            if (mn < L[i]) { // uh oh
                cout << "No\n";
                return;
            }
        }
    }
    cout << "Yes\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t; while (t--)
        solve();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23