Codeforces 1284D - New Year and Conference 题解

题解 #

题目本质是判断能否找到一对线段使得他们在一个维度上相交但不在另一维度上不相交。为了得到所有相交的线段，我们要知道对于所有时间点被哪些线段覆盖了。具体一点就是需要几个数组 $open_i$ 和 $close_i$ ，分别存的是以 $i$ 开头和结尾的线段。那么我们如何知道是否有一对线段不相交呢？我们还需要维护两个 multiset，一个存当前线段的起点，另一个存终点。如果最右边的起点大于最左边的终点那么就说明有两个线段没重叠。

最后别忘了离散化并且两个维度都要检查一下。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define pb push_back
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
typedef vector<int> vi;
bool check(vi& sa,vi& ea,vi& sb,vi& eb,int m){
    vector<vector<int>> l(m),r(m);
    int n=sa.size();
    forn(i,n){
        l[sa[i]].pb(i);
        r[ea[i]].pb(i);
    }
    multiset<int,greater<int>> lmax;
    multiset<int> rmin;
    forn(i,m){
        for(auto id:l[i]) lmax.insert(sb[id]),rmin.insert(eb[id]);
        if(!empty(lmax)&& *lmax.begin()> *rmin.begin()) return 0;
        for(auto id:r[i]){
            lmax.erase(lmax.find(sb[id])); rmin.erase(rmin.find(eb[id]));
        }
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int> sa(n),sb(n),ea(n),eb(n);
    forn(i,n) rd(sa[i],ea[i],sb[i],eb[i]);
    vector<int> time;time.reserve(4*n);
    for(auto it:sa) time.pb(it);
    for(auto it:ea) time.pb(it);
    for(auto it:sb) time.pb(it);
    for(auto it:eb) time.pb(it);
    sort(all(time));
    time.resize(unique(all(time))-time.begin());
    forn(i,n){
        sa[i]=lower_bound(all(time),sa[i])-time.begin();
        ea[i]=lower_bound(all(time),ea[i])-time.begin();
        sb[i]=lower_bound(all(time),sb[i])-time.begin();
        eb[i]=lower_bound(all(time),eb[i])-time.begin();
    }
    if(check(sa,ea,sb,eb,time.size())&& check(sb,eb,sa,ea,time.size())) cout<<"YES";
    else cout<<"NO";
 
    return 0;
}