记录编号	618115	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4455.interval	最终得分	100
用户昵称	HXF	是否通过	通过
代码语言	C++	运行时间	6.615 s
提交时间	2026-08-26 16:49:21	内存使用	23.15 MiB

#include<bits/stdc++.h>
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
using namespace std;
void chkmax(int &a,int b){a=max(a,b);}
void chkmin(int &a,int b){a=min(a,b);}
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
inline ll rell()
{
    int f=1;ll num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=250010;
int last[N],resc[N],resq[N];
vector<pir> qs[N];
int a[N],b[N],l[N],r[N];
int n,q;
struct bit
{
    int c[N];
    void add(int w,int z){while(w) c[w]+=z,w-=w&-w;return;}
    int query(int w){int res=0;while(w<=n) res+=c[w],w+=w&-w;return res;}
}tr1,tr2;
struct node
{
    int l,r;
    mutable int val;
};
bool operator <(const node &a,const node &b)
{
    if(a.l==b.l) return a.r<b.r;
    else return a.l<b.l;
}
vector<int> ys;
set<node> s;
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) a[i]=re(),b[i]=re();
    for(int i=1;i<=q;i++) l[i]=re()+1,r[i]=re()+1;

    for(int i=1;i<=n;i++) ys.pb(b[i]);
    sort(ys.begin(),ys.end());
    ys.erase(unique(ys.begin(),ys.end()),ys.end());
    for(int i=1;i<=q;i++) qs[r[i]].pb(mp(l[i],i));
    s.insert((node){1,1000000000,0});
    for(int i=1;i<=n;i++)
    {
        int ysb=lower_bound(ys.begin(),ys.end(),b[i])-ys.begin()+1;
        if(last[ysb]) tr1.add(last[ysb],-1);
        last[ysb]=i;
        tr1.add(i,1);
        for(auto [ql,bi]:qs[i]) resc[bi]=tr1.query(ql);

        auto itr=s.lower_bound((node){b[i]+1,0,0});itr--;
        if(itr->r!=b[i])
        {
            int tmpl=itr->l,tmpr=itr->r,val=itr->val;
            s.erase(itr);
            s.insert((node){tmpl,b[i],val});
            itr=s.insert((node){b[i]+1,tmpr,val}).fi;
        }
        else itr++;
        auto itl=s.lower_bound((node){a[i]+1,0,0});itl--;
        if(itl->l!=a[i])
        {
            int tmpl=itl->l,tmpr=itl->r,val=itl->val;
            s.erase(itl);
            s.insert((node){tmpl,a[i]-1,val});
            itl=s.insert((node){a[i],tmpr,val}).fi;
        }
        for(auto it=itl;it!=itr;it++) tr2.add(it->val,-(it->r-it->l+1));
        s.erase(itl,itr);
        tr2.add(i,b[i]-a[i]+1);
        s.insert((node){a[i],b[i],i});
        for(auto [ql,bi]:qs[i]) resq[bi]=tr2.query(ql);
    }
    for(int i=1;i<=q;i++) if(resc[i]==resq[i]) printf("1 ");else printf("0 ");
    printf("\n");
    return 0;
}