QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91175#6136. AirdropRandom_CodeWA 536ms17528kbC++111.9kb2023-03-27 16:12:512023-03-27 16:12:55

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-27 16:12:55]
  • 评测
  • 测评结果:WA
  • 用时:536ms
  • 内存:17528kb
  • [2023-03-27 16:12:51]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
ll n,ty,dx[N],dy[N],pre[N],suf[N];
vector<ll> allv,vt[N];
int main(){
	ll T,i,j;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&n,&ty);
		allv.clear();
		for(i=0;i<n;i++)
		{
			scanf("%lld%lld",&dx[i],&dy[i]);
			allv.push_back(dx[i]);
		}
		sort(allv.begin(),allv.end());
		allv.erase(unique(allv.begin(),allv.end()),allv.end());
		for(i=0;i<allv.size();i++)
		{
			vt[i].clear();
		}
		for(i=0;i<n;i++)
		{
			vt[lower_bound(allv.begin(),allv.end(),dx[i])-allv.begin()].push_back(abs(ty-dy[i]));
		}
		set<ll> st;
		pre[0]=0;
		for(i=0;i<allv.size();i++)
		{
			sort(vt[i].begin(),vt[i].end());
			for(j=0;j<vt[i].size();j++)
			{
				if(j+1<vt[i].size()&&vt[i][j]==vt[i][j+1])
				{
					if(st.find(allv[i]-vt[i][j])!=st.end())
					{
						st.erase(allv[i]-vt[i][j]);
					}
					j++;
					continue;
				}
				if(st.find(allv[i]-vt[i][j])!=st.end())
				{
					st.erase(allv[i]-vt[i][j]);
				}
				else
				{
					st.insert(allv[i]-vt[i][j]);
				}
			}
			pre[i+1]=st.size();
		}
		st.clear();
		suf[allv.size()]=0;
		for(i=allv.size()-1;i>=0;i--)
		{
			for(j=0;j<vt[i].size();j++)
			{
				if(j+1<vt[i].size()&&vt[i][j]==vt[i][j+1])
				{
					if(st.find(allv[i]+vt[i][j])!=st.end())
					{
						st.erase(allv[i]+vt[i][j]);
					}
					j++;
					continue;
				}
				if(st.find(allv[i]+vt[i][j])!=st.end())
				{
					st.erase(allv[i]+vt[i][j]);
				}
				else
				{
					st.insert(allv[i]+vt[i][j]);
				}
			}
			suf[i]=st.size();
		}
		ll mx=pre[allv.size()],mn=pre[allv.size()];
		for(i=0;i<allv.size();i++)
		{
			mx=max(mx,pre[i]+suf[i+1]+(ll)vt[i].size());
			mn=min(mn,pre[i]+suf[i+1]+(ll)vt[i].size());
			if(i==allv.size()-1||allv[i]+1!=allv[i+1])
			{
				mx=max(mx,pre[i]+suf[i]);
				mn=min(mn,pre[i]+suf[i]);
			}
		}
		printf("%lld %lld\n",mn,mx);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5900kb

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: 536ms
memory: 17528kb

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
4 6
2 6
0 2
4 4
2 2
4 4
4 7
4 4
9 9
4 6
0 3
4 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
3 7
1 1
4 6
2 4
3 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
2 2
2 5
3 3
1 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:

wrong answer 7th numbers differ - expected: '2', found: '4'