QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91760#6136. AirdropzhouhuanyiWA 176ms10660kbC++231.7kb2023-03-29 15:31:292023-03-29 15:31:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 15:31:32]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:10660kb
  • [2023-03-29 15:31:29]
  • 提交

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;
}

詳細信息

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'