社区讨论

70pts求debug

P11232[CSP-S 2024] 超速检测参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m38hx9d4
此快照首次捕获于
2024/11/08 16:49
去年
此快照最后确认于
2024/11/08 20:10
去年
查看原帖
CPP
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t;
int n,m,l,V;
inline int read(){
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0' || ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
struct node{
	int C[2];
	bool operator<(const node &rhs){
		return C[1]<rhs.C[1] || (C[1]==rhs.C[1] && C[0]>=rhs.C[0]);
	}
}c[100005];
int tot,p[1000005],choose[1000005];
int main(){
	t=read();
	while(t--){ 
		tot=0;
		memset(p,0,sizeof p);
		memset(choose,0,sizeof choose);
		n=read();
		m=read();
		l=read();
		V=read();
		for(int i=1;i<=n;i++){
			int d,v,a;
			d=read();
			v=read();
			a=read();
			if(v<=V && a<=0)continue;
			if(a==0){
				tot++;
				c[tot].C[0]=d;
				c[tot].C[1]=l;
			}else if(a>0){
				if(v>V){
					tot++;
					c[tot].C[0]=d;
					c[tot].C[1]=l;
				}else{
					int x=(V*V-v*v)/(2*a);
					if(d+x+1<=l){
						tot++;
					}else{
						continue;
					}
					c[tot].C[0]=d+x+1;
					c[tot].C[1]=l;
				}
			}else{
				int x=(v*v-V*V)/(-2*a)+int((v*v-V*V)%(-2*a)>0);
				tot++;
				c[tot].C[0]=d;
				c[tot].C[1]=min(d+x-1,l);
			}
		}
		int ans1=0;
		for(int i=1;i<=m;i++){
			int temp;
			temp=read();
			p[temp]++;
		}
		for(int i=1;i<=l;i++){
			p[i]+=p[i-1];
		}
		for(int i=1;i<=tot;i++){
			if(p[c[i].C[1]]-(c[i].C[0]?p[c[i].C[0]-1]:0)){
				ans1++;
			}
		}
		sort(c+1,c+tot+1);
		for(int i=1;i<=tot;i++){
			for(int j=c[i-1].C[1]+1;j<=c[i].C[1];j++){
				choose[j]+=choose[j-1];
			}
			if((p[c[i].C[1]]-(c[i].C[0]?p[c[i].C[0]-1]:0))==0 || choose[c[i].C[1]]-(c[i].C[0]?choose[c[i].C[0]-1]:0)>0){
				continue;
			}else{
				int L=c[i].C[0],R=c[i].C[1];
				while(L<R){
					int mid=(1+L+R)>>1;
					if(p[mid]<p[c[i].C[1]]){
						L=mid;
					}else{
						R=mid-1;
					}
				}
				for(int j=L+1;j<=c[i].C[1];j++){
					choose[j]++;
				}
			}
		}
		
		printf("%d %d\n",ans1,m-choose[c[tot].C[1]]);
	}
	return 0;
}
WA了7、8、10三组,样例第五组的后半部分第二个数有小偏差求debug

回复

2 条回复,欢迎继续交流。

正在加载回复...