求hack
查看原帖
求hack
271642
Evier楼主2021/5/18 22:13

rt

和正解拍了几万组没拍出错,但只有十分,都是前几行错的

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
int n,m;
int c[10000005],ans[500005];
bool v[500005];
void add(int x,int y){
	for(;x<=1e7;x+=x&-x)c[x]+=y;
}
int ask(int x){
	int ans=0;
	for(;x;x-=x&-x)ans+=c[x];
	return ans;
}
struct node{
	int op,x,y,a,b;
}q[1500005];
bool cmp(node x,node y){
	return x.x<y.x;
}
signed main(){
	freopen("data.in","r",stdin);
	freopen("s.out","w",stdout);
	n=read();m=read();
	int tot=0;
	for(int i=1;i<=n;i++){
		q[++tot].op=0;q[tot].x=read(),q[tot].y=read();
		q[tot].x++;q[tot].y++;
	}
	for(int i=1;i<=m;i++){
		q[++tot].op=i;q[tot].x=read();q[tot].y=read();q[tot].a=read();q[tot].b=read();
		q[tot].a++;q[tot].y++;q[tot].b++;
		q[++tot].op=i;q[tot].x=q[tot-1].a;q[tot].y=q[tot-1].b;q[tot].a=q[tot-1].x,q[tot].b=q[tot-1].y;
	}
	sort(q+1,q+tot+1,cmp);
	for(int i=1;i<=tot;i++){
		if(!q[i].op)add(q[i].y,1);
		else{
			if(!v[q[i].op]){
				v[q[i].op]=1;
				ans[q[i].op]+=ask(q[i].b)-ask(q[i].y-1);
			}
			else{
				ans[q[i].op]=ask(q[i].y)-ans[q[i].op]-ask(q[i].b-1);
			}
		}
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}
2021/5/18 22:13
加载中...