QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#534182 | #6136. Airdrop | Tomato_Fish | AC ✓ | 474ms | 14128kb | C++14 | 2.0kb | 2024-08-26 21:46:15 | 2024-08-26 21:46:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
struct node{
int x,y;
}g[N];
map<int,int> B,C;
int qz1[N],qz2[N],Type[N],Las[N];
bool cmp(node n1,node n2) {return (n1.x<n2.x);}
int main()
{
int T;
scanf("%d",&T);
while(T--){
int n,y0;
scanf("%d%d",&n,&y0);
for(int i=1;i<=n;i++) scanf("%d%d",&g[i].x,&g[i].y);
sort(g+1,g+n+1,cmp);
B.clear();qz1[0]=0;
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++){
int tmp=abs(g[i].y-y0)-g[i].x;
if(B[tmp]==0) B[tmp]=++cnt1;
tmp=B[tmp];
if(Type[tmp]==0){
if(Las[tmp]!=g[i].x)
Type[tmp]=1,qz1[i]=qz1[i-1];
else
qz1[i]=qz1[i-1]+1;
}
else{
Type[tmp]=0;
Las[tmp]=g[i].x;
qz1[i]=qz1[i-1]+2;
}
}
for(int i=1;i<=cnt1;i++) Type[i]=Las[i]=0;
C.clear();qz2[n+1]=0;
for(int i=n;i>=1;i--){
int tmp=abs(g[i].y-y0)+g[i].x;
if(C[tmp]==0) C[tmp]=++cnt2;
tmp=C[tmp];
if(Type[tmp]==0){
if(Las[tmp]!=g[i].x)
Type[tmp]=1,qz2[i]=qz2[i+1];
else
qz2[i]=qz2[i+1]+1;
}
else{
Type[tmp]=0;
Las[tmp]=g[i].x;
qz2[i]=qz2[i+1]+2;
}
}
for(int i=1;i<=cnt2;i++) Type[i]=Las[i]=0;
int las=0,mx=qz2[1],mn=qz2[1];
for(int i=1;i<=n;i++)
if(i==n||g[i].x!=g[i+1].x){
mx=max(mx,qz1[las]+qz2[i+1]);
mn=min(mn,qz1[las]+qz2[i+1]);
if(i==n||g[i+1].x-1>g[i].x){
mx=max(mx,qz1[i]+qz2[i+1]);
mn=min(mn,qz1[i]+qz2[i+1]);
}
las=i;
}
printf("%d %d\n",n-mx,n-mn);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3912kb
input:
3 3 2 1 2 2 1 3 5 3 3 2 1 2 5 4 3 2 3 1 3 4 3
output:
1 3 0 3 2 2
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 474ms
memory: 14128kb
input:
3508 6 1 7 1 1 1 9 1 10 1 3 1 4 1 3 8 8 9 8 7 1 8 9 5 10 1 10 8 10 2 5 1 9 9 5 9 10 9 6 4 4 7 6 7 10 5 3 8 9 5 9 9 7 5 4 7 10 5 6 9 9 5 6 6 9 3 3 2 5 1 3 8 6 4 5 9 10 2 2 9 10 10 10 8 4 1 7 1 6 1 3 1 5 1 2 4 9 3 3 3 4 5 3 8 9 6 9 9 6 3 9 5 9 3 2 9 9 1 9 2 4 1 5 4 5 6 6 5 9 8 4 1 2 1 5 1 7 1 3 1 9 10...
output:
6 6 1 3 1 5 2 6 2 6 0 2 4 4 2 2 4 4 4 7 4 4 9 9 4 6 0 3 2 6 2 2 2 6 10 10 9 9 1 3 2 4 0 2 2 4 4 7 6 6 9 9 2 2 2 2 3 5 1 4 2 2 1 1 3 5 4 7 3 6 1 1 5 7 5 5 1 3 2 2 1 7 1 1 4 6 2 4 2 6 2 4 1 7 2 4 9 9 0 3 1 1 3 8 2 2 2 2 9 9 3 7 4 4 4 6 2 5 0 2 2 5 3 3 0 4 4 4 2 4 2 2 4 6 6 6 6 6 0 2 2 6 2 4 2 6 2 5 1 ...
result:
ok 7016 numbers