28分求调
查看原帖
28分求调
1277599
Zengzhangchen楼主2024/11/22 17:08
#include<bits/stdc++.h>
using namespace std;
int a,b,c,ans[200005],aa[200005],n,q;
char x,s,s2;
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d%c%c%d%c%d",&a,&x,&s,&b,&s2,&c);
		if(s=='+'){
			ans[i]=int(c-b)/a;
		}else{
			ans[i]=(c+b)/a;
		}
	}
	//答案求对了吗?? 
	//for(int i=1;i<=n;i++)cout<<"i="<<i<<" ans="<<ans[i]<<endl;
	sort(ans+1,ans+n+1);
	int len=0;
	for(int i=1;i<=n;i++){
		if(ans[i]!=ans[i-1])aa[++len]=ans[i];
	}
	//去重对了吗?? 
	//for(int i=1;i<=l;i++)cout<<aa[i]<<" ";
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		int ll=1,rr=len,ansl,ansr;
		while(ll<=rr){
			int mid=ll+rr>>1;
			if(aa[mid]>=l){
				ansl=mid;
				rr=mid-1;
			}else ll=mid+1;
		}
		ll=1,rr=len;
		while(ll<=rr){
			int mid=ll+rr>>1;
			if(aa[mid]<=r){
				ansr=mid;
				ll=mid+1;
			}else rr=mid-1;
		}
		//查找对了吗
		cout<<ansr-ansl+1<<endl;
	}
	return 0;
}
2024/11/22 17:08
加载中...