Educational Codeforces Round 27 C. Two TVs（模拟）

水深无声 2022-06-10 14:39 154阅读 0赞

C. Two TVs

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp is a great fan of television.

He wrote down all the TV programs he is interested in for today. His list contains *n* shows, *i*\-th of them starts at moment *l**i* and ends at moment *r**i*.

Polycarp owns two TVs. He can watch two different shows simultaneously with two TVs but he can only watch one show at any given moment on a single TV. If one show ends at the same moment some other show starts then you can't watch them on a single TV.

Polycarp wants to check out all *n* shows. Are two TVs enough to do so?

Input

The first line contains one integer *n* (1 ≤ *n* ≤ 2·105) — the number of shows.

Each of the next *n* lines contains two integers *l**i* and *r**i* (0 ≤ *l**i* < *r**i* ≤ 109) — starting and ending time of *i*\-th show.

Output

If Polycarp is able to check out all the shows using only two TVs then print "YES" (without quotes). Otherwise, print "NO" (without quotes).

Examples

input

3
    1 2
    2 3
    4 5

output

YES

input

4
    1 2
    2 3
    2 3
    1 2

output

题解：

题意：

有两台电视，有节目的开始时间和结束时间，这题的题意还蛮有意思，你可以同时看两个节目，但是你在一个节目结束的时刻不能用这一台开下一个这个时刻开始的节目（但是可以换一台看），问你是否可以看完所有节目，直接模拟两个电视的关闭情况就行了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    struct node
    {
        int s,t;
        int d;
    }a[200005];
    int cmp(node x,node y)//节目开始时间从小到大排，相同结束时间早的在前
    {
        if(x.s!=y.s)
            return x.s<y.s;
        return x.t<y.t;
    }
    struct tv
    {
        int e;//记录电视节目的结束时间
        int tag;//记录电视的开闭
    }t[5];
    int main()
    {
        int i,j,n,flag=1;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].s,&a[i].t);
        }
        sort(a,a+n,cmp);
        t[0].e=-1;
        t[1].e=-1;
        t[0].tag=0;
        t[1].tag=0;
        for(i=0;i<n;i++)//模拟电视的开闭
        {
            if(a[i].s>t[0].e)//根据节目的结束时间清除电视的状态
            {
                t[0].tag=0;
            }
            if(a[i].s>t[1].e)
            {
                t[1].tag=0;
            }
            if(!t[0].tag)//如果第一台可以看
            {
                t[0].tag=1;
                t[0].e=a[i].t;
            }
            else if(!t[1].tag)
            {
                 t[1].tag=1;
                 t[1].e=a[i].t;
            }
            else
            {
                flag=0;
                break;
            }
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
        return 0;
    }