1 条题解
-
0
#include<bits/stdc++.h> #define N 300010 #define mid ((l+r)>>1) #define ls a[t].l #define rs a[t].r using namespace std;int x,y,cnt,rt[N]; struct dt{int c,l,r;}a[N*30],e[N];inline void bil(int &t,int k){a[t=++cnt]=a[k];} void upd(int t,int l,int r) { if (l==r) a[t].c=max(a[t].c,y);else{if (x<=mid) bil(ls,ls),upd(ls,l,mid); else bil(rs,rs),upd(rs,mid+1,r);a[t].c=min(a[ls].c,a[rs].c);} } int qry(int t,int l,int r) { if (x<=l && r<=y) return a[t].c; return min(x<=mid?qry(ls,l,mid):2e9,y>mid?qry(rs,mid+1,r):2e9); } int main() { int n,m,k,i,c,d;scanf("%d%d%d",&n,&m,&k); for (i=1;i<=k;i++) scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].c); sort(e+1,e+k+1,[](const dt&x,const dt&y){return x.r<y.r;}); for (i=1;i<=k;i++) bil(rt[i],rt[i-1]),x=e[i].c,y=e[i].l,upd(rt[i],1,n); while (m--) { scanf("%d%d%d%d",&x,&y,&c,&d);int l=0,r=k+1; while (l<r-1) e[mid].r<=d?l=mid:r=mid; puts(qry(rt[l],1,n)>=c?"yes":"no");cout.flush(); } }
- 1
信息
- ID
- 6854
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者