文件详细信息

下载本文件

本文件的大小为 1630 字节。

#include<algorithm>
#include<cstdio>
int read(){
	bool flag=true;
	int ch=getchar(),num=0ll;
	while(ch<48||ch>57){
		if(ch=='-')flag=false;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return flag?num:-num;
}
const int maxn=200005;
int n,m,x1[maxn],x2[maxn],s[maxn],ans[maxn];
struct bullet{
	int x,id;
}a[maxn];
bool operator<(bullet a,bullet b){
	return a.x<b.x;
}
int total,root[maxn],left[maxn<<5],right[maxn<<5],val[maxn<<5];
void pushup(int u){
	val[u]=val[left[u]]+val[right[u]];
}
void build(int&u,int l,int r){
	u=++total;
	if(l==r)return;
	int m=(l+r)>>1;
	build(left[u],l,m);
	build(right[u],m+1,r); 
}
void update(int pre,int&u,int l,int r,int x){
	u=++total;
	if(l==r){
		val[u]++;
		return;
	}
	int m=(l+r)>>1;
	if(x<=m){
		update(left[pre],left[u],l,m,x);
		right[u]=right[pre];
	}else{
		left[u]=left[pre];
		update(right[pre],right[u],m+1,r,x);
	}
	pushup(u);
}
int query(int pre,int u,int l,int r,int k){
	if(!u)return 0;
	if(l==r)return l;
	if(val[u]-val[pre]<k)return 0;
	int m=(l+r)>>1,sum=val[left[u]]-val[left[pre]];
	if(k<=sum)return query(left[pre],left[u],l,m,k);
	return query(right[pre],right[u],m+1,r,k-sum);
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)x1[i]=read(),x2[i]=read(),s[i]=read();
	for(int i=1;i<=m;i++)a[i].x=read(),a[i].id=i;
	std::sort(a+1,a+m+1);
	build(root[0],1,n);
	for(int i=1;i<=m;i++)update(root[a[i-1].x],root[a[i].x],1,m,a[i].id);
	for(int i=1;i<=200000;i++)
		if(!root[i])
			root[i]=root[i-1];
	for(int i=1;i<=n;i++)ans[query(root[x1[i]-1],root[x2[i]],1,m,s[i])]++;
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}