60pts WA on #5#6#8#10
查看原帖
60pts WA on #5#6#8#10
998158
fire_hmz楼主2024/11/5 15:50

rt,第一问的问题,和正确答案差±1或0

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define u_m unordered_map
#define Ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int n,m,l,v;
struct node{
	int x;
	int y;
	int id;
}a[100005];
int b[100005];
bool bb[100005];
bool cmp(node x,node y){
	if(x.x==y.x) return x.y<y.y;
	return x.x<y.x;
}
bool dmp(node x,node y){
	return x.y<y.y;
}
signed main(){
	Ios
	freopen("detect5.in","r",stdin);
	freopen("detect.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m>>l>>v;
		for(int i=1;i<=n;i++){
			int x,y,z;
			cin>>x>>y>>z;
			a[i].id=i;
			if(z==0){
				if(y>v){
					a[i].x=x;
					a[i].y=l+1;
					
				}
				else {
					a[i].x=a[i].y=l+1;
				}
			}
			else{
				if(z<0){
					if(y<v) {
						a[i].x=l+1;
						a[i].y=l+1;
//						cout<<i<<"trret\n";
						continue;
					}
					a[i].x=x;
					a[i].y=x+abs((v*v-y*y)/(z+z));
				}
				else{
					if(y>v) {
						a[i].x=x;
						a[i].y=l+1;
//						cout<<i<<"trret\n";
						continue;
					}
					a[i].x=x+max(0ll,(int)ceil((double)(v*v-y*y)/(double)(z+z)));
					a[i].y=l+1;
				}
			}
//			cout<<a[i].x<<' '<<a[i].y<<endl;
		}
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=m;i++) cin>>b[i];
		sort(b+1,b+m+1);
		int j=1;
		int cnt=0;
		for(int i=1;i<=n;i++){
//			cout<<a[i].x<<' '<<a[i].y<<endl;
			if(a[i].x>b[j]) {
				j++;
				i--;
				continue;
			}
			if(j>m) break;
			if(b[j]>=a[i].x&&b[j]<=a[i].y){
				cnt++;
				bb[a[i].id]=1;
			}
		}
		cout<<cnt<<' ';
		sort(a+1,a+n+1,dmp);
		cnt=0;
		l=0;
		for(int i=1;i<=n;i++){
			if(bb[a[i].id]){
				if(!(a[i].x<=b[l]&&a[i].y>=b[l])){
					l++;
					while(l<=m&&a[i].y>=b[l]) {
						l++;
//						cout<<b[l]<<endl;
					}
					l--;
					cnt++;
					if(l>m) break;
				}
				bb[a[i].id]=0;
			}
		}
		cout<<m-cnt<<'\n';
	}
	return 0;
}
/*

*/

2024/11/5 15:50
加载中...