Thallium54

Tutorial for Codeforces 1284D - New Year and Conference

Data Structure Solutions

Solution #

The problem can be described as checking if there exists a pair of conferences that overlap in one dimension but not in the other dimension. In order to get all the segments that overlap with each other, we should know for all time points, which segments cover it. Specifically, we need some arrays openiopen_i and closeiclose_i which store the segments that start at ii and close at ii. So how can we know if there’s a pair of segments that doesn’t overlap on another dimension? We can maintain two multisets, one is the starting points of the current segments, the other is the end points. If the rightmost starting is bigger than the leftmost end point, this means that there exists a pair of segments that doesn’t overlap.

Note that we need to compress the time points and check both dimension.

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;
}