Filled with optimism, Hyunuk will host a conference about how great this new year will be!

The conference will have 𝑛 lectures. Hyunuk has two candidate venues 𝑎 and 𝑏. For each of the 𝑛 lectures, the speaker specified two time intervals [𝑠𝑎𝑖,𝑒𝑎𝑖] (𝑠𝑎𝑖≤𝑒𝑎𝑖) and [𝑠𝑏𝑖,𝑒𝑏𝑖] (𝑠𝑏𝑖≤𝑒𝑏𝑖). If the conference is situated in venue 𝑎, the lecture will be held from 𝑠𝑎𝑖 to 𝑒𝑎𝑖, and if the conference is situated in venue 𝑏, the lecture will be held from 𝑠𝑏𝑖 to 𝑒𝑏𝑖. Hyunuk will choose one of these venues and all lectures will be held at that venue.

Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval [𝑥,𝑦] overlaps with a lecture held in interval [𝑢,𝑣] if and only if max(𝑥,𝑢)≤min(𝑦,𝑣).

We say that a participant can attend a subset 𝑠 of the lectures if the lectures in 𝑠 do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue 𝑎 or venue 𝑏 to hold the conference.

A subset of lectures 𝑠 is said to be venue-sensitive if, for one of the venues, the participant can attend 𝑠, but for the other venue, the participant cannot attend 𝑠.

A venue-sensitive set is problematic for a participant who is interested in attending the lectures in 𝑠 because the participant cannot be sure whether the lecture times will overlap. Hyunuk will be happy if and only if there are no venue-sensitive sets. Determine whether Hyunuk will be happy.

链接🔗

「CodeForces 1284D」New Year and Conference

题解

一种很优美的做法,代码量少
参考 xht37's blog
这里对其代码进行解释

代码

const ll maxd = 1e5+10;

ll sa[maxd],sb[maxd],ea[maxd],eb[maxd],a[maxd*4];
ll n,m,tot;
V l[maxd*4],r[maxd*4];


ll solve()
{
    FOR(i,1,m) l[i].clear(),r[i].clear();
    FOR(i,1,n) l[sa[i]].pb(i), r[ea[i]].pb(i); // l表示在时间i,有那些会议开始了,r表示结束了
    multiset<ll,greater<ll> > L;
    multiset<ll> R;
    FOR(i,1,m)      //枚举时间
    {
        for(ll x:l[i]) L.insert(sb[x]), R.insert(eb[x]); // 因为会议x开始了,所以将再另一边的会议丢进集合,也表示开始了
        if(L.size() && *L.begin() > *R.begin()) return 1ll; // 如果在集合中出现了断点,说明没有相交,而此时我们枚举的会议都是相交的,所以这里会出现 venue-sensitive
        for(ll x:r[i]) L.erase(sb[x]),R.erase(eb[x]);
    }
    return 0ll;
}

int main()
{
//    __IN;__OUT;
    RLL(n);
    FOR(i,1,n) RLL4(sa[i],ea[i],sb[i],eb[i]);
    FOR(i,1,n) a[++tot] = sa[i];
    FOR(i,1,n) a[++tot] = sb[i];
    FOR(i,1,n) a[++tot] = ea[i];
    FOR(i,1,n) a[++tot] = eb[i];
    sort(a+1,a+1+tot);
    m = unique(a+1,a+1+tot) - a - 1; // 因为要枚举时间,所以需要离散化
    FOR(i,1,n) sa[i] = lower_bound(a+1,a+1+m,sa[i]) - a;
    FOR(i,1,n) sb[i] = lower_bound(a+1,a+1+m,sb[i]) - a;
    FOR(i,1,n) ea[i] = lower_bound(a+1,a+1+m,ea[i]) - a;
    FOR(i,1,n) eb[i] = lower_bound(a+1,a+1+m,eb[i]) - a;
    ll flag = solve(); swap(sa,sb);swap(ea,eb); flag|= solve();

    if(flag) PS("NO"); else PS("YES");

    return 0;
}