Submission #1187590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187590		browntoad	Jail (JOI22_jail)	C++20	5 / 100	32 ms	3504 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n) 
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

const ll maxn = 5e5+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

ll pw(ll a, ll p){
    ll rt = 1;
    while(p > 0){
        if (p & 1){
            rt *= a;
            rt %= mod;
        }
        a *= a;
        a %= mod;
        p >>= 1;
    }
    return rt;
}
ll inv(int a){
    return pw(a, mod-2);
}

signed main(){
    IOS();
    int Q; cin>>Q;
    while(Q--){
        int n; cin>>n;
        REP(i, n-1){
            int u,v; cin>>u>>v;
        }
        int m; cin>>m;
        vector<pii> rng1, rng2;
        REP(i, m){
            int l, r; cin>>l>>r;
            if (l < r) rng1.pb({l, r});
            else rng2.pb({r, l});
        }
        vector<int> pf(n+2);
        bool gg = false;
        for (auto pp:rng1) {
            pf[pp.f]++;
            pf[pp.s+1]--;
        }
        REP1(i, n) pf[i] += pf[i-1];
        REP1(i, n) pf[i] += pf[i-1];
        for (auto pp:rng2){
            if(pf[pp.s] - pf[pp.f-1] > 0){
                gg = 1;
                break;
            }
        }

        sort(ALL(rng1)); sort(ALL(rng2));
        int mx = 0;
        for (auto pp:rng1){
            if(mx > pp.s){
                gg = 1;
                break;
            }
            mx = max(mx, pp.s);
        }
        mx = 0;
        for (auto pp:rng2){
            if (mx > pp.s) {
                gg = 1;
                break;
            }
            mx = max(mx, pp.s);
        }
        cout<<(gg?"No":"Yes")<<endl;
    }
}

• Subtask 1: 5 / 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