Submission #1244067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244067		sula2	Jail (JOI22_jail)	C++20	0 / 100	1 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);
    }
};

bool check(int n, vector<pair<int,int>> A, vector<pair<int,int>> B) {
    segtree s(n);
    for (auto [l, r] : A) {
        s.update(r, l);
    }
    for (auto [l, r] : B) {
        int mn = s.query(l, r);
        if (mn < l) return false;
    }
    return true;
}

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];
    vector<pair<int,int>> ltr, rtl;
    for (int i = 0; i < m; i++) {
        cin >> L[i] >> R[i];
        L[i]--, R[i]--;
        (L[i] < R[i] ? ltr : rtl).emplace_back(L[i], R[i]);
    }
    for (auto& [l, r] : rtl) swap(l, r);
    if (!check(n, ltr, rtl) || !check(n, rtl, ltr)) {
        cout << "No\n";
        return;
    }
    int pref[n]{};
    for (int i = 0; i < m; i++) {
        if (L[i] > R[i]) swap(L[i], R[i]);
        pref[L[i]]++;
        if (R[i] != n-1) pref[R[i] + 1]--;
    }
    for (int i = 1; i < n; i++)
        pref[i] += pref[i-1];
    segtree s(n);
    for (int i = 0; i < n; i++)
        s.update(i, pref[i]);
    for (int i = 0; i < m; i++) {
        int mn = s.query(L[i], R[i]);
        if (mn == 2) {
            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