Hello 2020 D. New Year and Conference

发表于 更新于 分类于

链接

https://codeforces.com/contest/1284/problem/D

题意

$n$ 节课，两个教室 $A,B$，在两个教室开始的时间分别为 $[a_i,b_i]$，$[c_i,d_i]$。

问是否不存在两节课满足同时在 $A/B$ 上时不会发生区间重叠，同时在 $B/A$ 上时会发生区间重叠。

思路

先考虑在 $A$ 上时会发生区间重叠，在 $B$ 上时不会发生区间重叠。

将 $n$ 节课按照 在 $A$ 上的开始时间从小到大排序。

枚举每门课，记当前枚举到 $i$，只考虑排在 $i$ 后与 $i$ 重叠，因为前面与 $i$ 重叠已在之前计算过。

二分找到开始时间比当前课结束时间大的最小下标 $pos$。

那么与 $i$ 重叠的课为 $[i+1,pos-1]$，考虑这些课在 $B$ 上是否与 $i$ 在 $B$ 上不重叠。

显然当在 $B$ 上结束时间的最小值小于 $i$ 在 $B$ 上的开始时间或者在 $B$ 上开始时间的最大值大于 $i$ 在 $B$ 上的结束时间时，存在与 $i$ 不重叠的课，用线段树维护。

在 $B$ 上时会发生区间重叠，在 $A$ 上时不会发生区间重叠的情况同上。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=1e5+5;
pair<PII,PII> a[N];
int n,b[N],ls[N<<2],rs[N<<2],mn[N<<2],mx[N<<2];
void build(int p,int l,int r) {
    ls[p]=l,rs[p]=r;
    if(l==r) {
        mn[p]=a[l].SE.SE;
        mx[p]=a[l].SE.FI;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    mn[p]=min(mn[p<<1],mn[p<<1|1]);
    mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
PII query(int p,int l,int r) {
    if(ls[p]>=l&&rs[p]<=r) return MP(mn[p],mx[p]);
    int mid=ls[p]+rs[p]>>1;
    if(r<=mid) return query(p<<1,l,r);
    if(l>mid) return query(p<<1|1,l,r);
    PII ll=query(p<<1,l,r),rr=query(p<<1|1,l,r);
    return MP(min(ll.FI,rr.FI),max(ll.SE,rr.SE));
}
bool cmp (pair<PII,PII> a,pair<PII,PII> b) {
    return a.FI.FI<b.FI.FI;
}
bool solve() {
    sort(a+1,a+1+n,cmp);
    int cnt=0;
    for(int i=1;i<=n;i++) b[++cnt]=a[i].FI.FI;
    build(1,1,n);
    for(int i=1;i<=n;i++) {
        int pos=upper_bound(b+1,b+1+n,a[i].FI.SE)-b-1;
        if(i+1>pos) continue;
        PII t=query(1,i+1,pos);
        if(t.FI<a[i].SE.FI||t.SE>a[i].SE.SE) return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].FI.FI>>a[i].FI.SE>>a[i].SE.FI>>a[i].SE.SE;
    if(!solve()) return cout<<"NO"<<'\n',0;
    for(int i=1;i<=n;i++) swap(a[i].FI,a[i].SE);
    cout<<(solve()?"YES":"NO")<<'\n';
    return 0;
}