社区讨论
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 条回复,欢迎继续交流。
正在加载回复...