[Hello 2020] D. New Year and Conference (ST表，排序)
D. New Year and Conference
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Filled with optimism, Hyunuk will host a conference about how great this new year will be!
The conference will have nn lectures. Hyunuk has two candidate venues aa and bb. For each of the nn lectures, the speaker specified two time intervals [sai,eai][sai,eai] (sai≤eaisai≤eai) and [sbi,ebi][sbi,ebi] (sbi≤ebisbi≤ebi). If the conference is situated in venue aa, the lecture will be held from saisai to eaieai, and if the conference is situated in venue bb, the lecture will be held from sbisbi to ebiebi. 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 [x,y][x,y] overlaps with a lecture held in interval [u,v][u,v] if and only if max(x,u)≤min(y,v)max(x,u)≤min(y,v).
We say that a participant can attend a subset ss of the lectures if the lectures in ss do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue aa or venue bb to hold the conference.
A subset of lectures ss is said to be venue-sensitive if, for one of the venues, the participant can attend ss, but for the other venue, the participant cannot attend ss.
A venue-sensitive set is problematic for a participant who is interested in attending the lectures in ss 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.
Input
The first line contains an integer nn (1≤n≤1000001≤n≤100000), the number of lectures held in the conference.
Each of the next nn lines contains four integers saisai, eaieai, sbisbi, ebiebi (1≤sai,eai,sbi,ebi≤1091≤sai,eai,sbi,ebi≤109, sai≤eai,sbi≤ebisai≤eai,sbi≤ebi).
Output
Print "YES" if Hyunuk will be happy. Print "NO" otherwise.
You can print each letter in any case (upper or lower).
Examples
input
Copy
2
1 2 3 6
3 4 7 8
output
Copy
YES
input
Copy
3
1 3 2 4
4 5 6 7
3 4 5 5
output
Copy
NO
input
Copy
6
1 5 2 9
2 4 5 8
3 6 7 11
7 10 12 16
8 11 13 17
9 12 14 18
output
Copy
YES
Note
In second example, lecture set {1,3}{1,3} is venue-sensitive. Because participant can't attend this lectures in venue aa, but can attend in venue bb.
In first and third example, venue-sensitive set does not exist.
题意：
给定n个表演，每一个表演在a和b场地的开始时间和结束时间分别是(sa,ea),(sb,eb)
如果有2个表演，只在一个场地（a或b），输出NO，否则输出YES
思路：
首先对这n个表演进行以sa为first标准，ea为second标准进行升序排序。
然后以sb和eb建立2个ST表，分别维护sb的区间最大值，eb的区间最小值。
枚举每一个表演，到第i个表演时，二分查找在\([sa_i,ea_i]\) 时间范围内开始的最后一个表演位置pos，
然后通过ST表询问 \([i+1,pos]\) 范围内的\(eb_{min},sb_{max}\)
如果\(eb_{min}<sb_i||sb_{max}>eb_i\) 说明在区间 \([i+1,pos]\) 存在一个表演在b场地与第i个表演不冲突，
将答案设为NO即可。以上我们只是处理了在a场地冲突时的b场地情况，
我们将 \((sa,ea)\) 和\((sb,eb)\) 交换后重复上面操作即可处理b场地冲突时的a场地情况。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
struct node
{
int sa, sb, ea, eb;
node() {}
node(int saa, int eaa, int sbb, int ebb)
{
sa = saa;
ea = eaa;
sb = sbb;
eb = ebb;
}
bool operator < (const node & b) const
{
if (sa != b.sa)
{
return sa < b.sa;
} else
{
return ea < b.ea;
}
}
};
node a[maxn];
int n;
int st1[maxn][25];//st表
int st2[maxn][25];//st表
void init(int n)
{
for (int i = 0; i < n; i++)
{
st1[i][0] = a[i + 1].sb;
st2[i][0] = a[i + 1].eb;
}
for (int i = 1; (1 << i) <= n; i++)
{
for (int j = 0; j + (1 << i) - 1 < n; j++)
{
st1[j][i] = max(st1[j][i - 1], st1[j + (1 << (i - 1))][i - 1]);
st2[j][i] = min(st2[j][i - 1], st2[j + (1 << (i - 1))][i - 1]);
}
}
}
int querysmax(int l, int r)
{
l--;
r--;
int k = (int)(log((double)(r - l + 1)) / log(2.0));
return max(st1[l][k], st1[r - (1 << k) + 1][k]);
}
int queryemin(int l, int r)
{
l--;
r--;
int k = (int)(log((double)(r - l + 1)) / log(2.0));
return min(st2[l][k], st2[r - (1 << k) + 1][k]);
}
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
n = readint();
repd(i, 1, n)
{
a[i].sa = readint();
a[i].ea = readint();
a[i].sb = readint();
a[i].eb = readint();
}
sort(a + 1, a + 1 + n);
init(n);
bool ans = 1;
repd(i, 1, n)
{
int pos = lower_bound(a + 1, a + 1 + n, node(a[i].ea, inf, 0, 0)) - a - 1;
if (!(i + 1 <= pos))continue;
if (queryemin(i + 1, pos) < a[i].sb || querysmax(i + 1, pos) > a[i].eb)
{
ans = 0;
}
}
repd(i, 1, n)
{
swap(a[i].sa, a[i].sb);
swap(a[i].ea, a[i].eb);
}
sort(a + 1, a + 1 + n);
init(n);
repd(i, 1, n)
{
int pos = lower_bound(a + 1, a + 1 + n, node(a[i].ea, inf, 0, 0)) - a - 1;
if (!(i + 1 <= pos))continue;
if (queryemin(i + 1, pos) < a[i].sb || querysmax(i + 1, pos) > a[i].eb)
{
ans = 0;
}
}
if (ans)
{
printf("YES\n");
} else
{
printf("NO\n");
}
return 0;
}
京公网安备 11010502036488号