QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91760 | #6136. Airdrop | zhouhuanyi | WA | 176ms | 10660kb | C++23 | 1.7kb | 2023-03-29 15:31:29 | 2023-03-29 15:31:32 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 300000
#define inf 1e9
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int x,y;
bool operator < (const reads &t)const
{
return x<t.x;
}
};
reads st[N+1];
int T,n,y0,minn,maxn,tong[N+1],cnt[N+1],cnt2[N+1],cnt3[N+1],length;
bool used[N+1];
int main()
{
int ps,ps2,res;
T=read();
while (T--)
{
n=read(),y0=read(),minn=inf,maxn=length=ps=res=0,ps2=1,tong[++length]=0;
for (int i=1;i<=n;++i) st[i].x=read(),st[i].y=read(),cnt[st[i].x]++,tong[++length]=st[i].x,tong[++length]=st[i].x+1;
sort(st+1,st+n+1),sort(tong+1,tong+length+1),length=unique(tong+1,tong+length+1)-tong-1;
for (int i=1;i<=n;++i)
{
cnt3[abs(st[i].y-y0)+st[i].x]++;
if (cnt3[abs(st[i].y-y0)+st[i].x]==1) res++;
if (cnt3[abs(st[i].y-y0)+st[i].x]==2) res--;
}
for (int i=1;i<=length;++i)
{
while (ps+1<=n&&st[ps+1].x<tong[i])
{
++ps,cnt2[abs(st[ps].y-y0)+100000-st[ps].x]++;
if (cnt2[abs(st[ps].y-y0)+100000-st[ps].x]==1) res++;
if (cnt2[abs(st[ps].y-y0)+100000-st[ps].x]==2) res--;
}
while (ps2<=n&&st[ps2].x<=tong[i])
{
cnt3[abs(st[ps2].y-y0)+st[ps2].x]--;
if (cnt3[abs(st[ps2].y-y0)+st[ps2].x]==1) res++;
if (!cnt3[abs(st[ps2].y-y0)+st[ps2].x]) res--;
++ps2;
}
minn=min(minn,res+cnt[tong[i]]),maxn=max(maxn,res+cnt[tong[i]]);
}
for (int i=1;i<=n;++i) cnt[st[i].x]--;
for (int i=1;i<=ps;++i) cnt2[abs(st[i].y-y0)+100000-st[i].x]--;
for (int i=ps2;i<=n;++i) cnt3[abs(st[i].y-y0)+st[i].x]--;
printf("%d %d\n",minn,maxn);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7640kb
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: -100
Wrong Answer
time: 176ms
memory: 10660kb
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 3 7 4 4 9 9 4 6 0 3 1 6 2 2 2 6 10 10 9 9 1 3 2 4 0 2 1 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 3 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 1 4 1 ...
result:
wrong answer 19th numbers differ - expected: '4', found: '3'