全WA求助,玄关
查看原帖
全WA求助,玄关
705296
miffy_123楼主2024/3/2 11:38
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 2147483646
#define inf 9223372036854775806
#define pl putchar('\n');
inline int read(){
	int f=1,k=0;
	char c;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		k=(k<<1)+(k<<3)+(c^48);
		c=getchar();
	}
	return f*k;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
vector<pair<int,int> >xy;
vector<tuple<int,int,int,int> >q;
const int maxn=1e7+5;
int a[maxn],ans[maxn];
inline int lowbit(int x){
	return x&(-x);
}
inline void update(int x,int k){
	for(register int i=x;i<maxn;i+=lowbit(i))a[i]+=k;
}
inline int getsum(int x){
	int ans=0;
	for(register int i=x;i>0;i-=lowbit(i))ans+=a[i];
	return ans;
}
int main(){
    int n,m;
    n=read(),m=read();
    for(register int i=1;i<=n;i++){
    	int x,y;
    	x=read(),y=read();
    	++x,++y;
    	xy.push_back(make_pair(x,y));
	}
	for(register int i=1;i<=m;i++){
		int x1,y1,x2,y2;
		x1=read(),y1=read(),x2=read(),y2=read();
		++x1,++y1,++x2,++y2;
		q.emplace_back(x2,y2,1,i);
		q.emplace_back(x1-1,y1-1,1,i);
		q.emplace_back(x1-1,y2,-1,i);
		q.emplace_back(x2,y1-1,-1,i);
	}
	sort(xy.begin(),xy.end());
	sort(q.begin(),q.end());
	int kk=0;
	for(auto [x,y,c,i]:q){
		while(kk<n&&xy[kk].first<=x)update(xy[kk].second,1),kk++;
		ans[i]+=c*getsum(y);
	}
	for(register int i=1;i<=m;i++)write(ans[i]),putchar(' ');
    return 0;
}


2024/3/2 11:38
加载中...