QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95921#6136. AirdropCSU2023WA 130ms17172kbC++143.3kb2023-04-12 14:55:002023-04-12 14:55:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-12 14:55:03]
  • 评测
  • 测评结果:WA
  • 用时:130ms
  • 内存:17172kb
  • [2023-04-12 14:55:00]
  • 提交

answer

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	char ch; bool flag = false; res = 0;
	while (ch = getchar(), !isdigit(ch) && ch != '-');
	ch == '-' ? flag = true : res = ch ^ 48;
	while (ch = getchar(), isdigit(ch))
		res = res * 10 + ch - 48;
	flag ? res = -res : 0;
}

template <class T>
inline void put(T x)
{
	if (x > 9)
		put(x / 10);
	putchar(x % 10 + 48);
}

template <class T>
inline void _put(T x)
{
	if (x < 0)
		x = -x, putchar('-');
	put(x);
}

template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}
template <class T>
inline void CkMax(T &x, T y) {x < y ? x = y : 0;}
template <class T>
inline T Min(T x, T y) {return x < y ? x : y;}
template <class T>
inline T Max(T x, T y) {return x > y ? x : y;}
template <class T>
inline T Abs(T x) {return x < 0 ? -x : x;}
template <class T>
inline T Sqr(T x) {return x * x;} 
// 若传入 int x 同时结果可能爆 int 应这样写 Sqr((ll)x) 

using std::map;
using std::set;
using std::pair;
using std::bitset;
using std::string;
using std::vector;
using std::complex;
using std::multiset;
using std::priority_queue;

typedef long long ll;
typedef long double ld;
typedef complex<ld> com;
typedef pair<int, int> pir;
const ld pi = acos(-1.0);
const ld eps = 1e-8;
const int N = 2e5 + 5;
const int Maxn = 1e9;
const int Minn = -1e9;
const int mod = 998244353;
const int lim = 1e5; 
int T_data, n, ys, bm, top;

inline void add(int &x, int y)
{
	x += y;
	x >= mod ? x -= mod : 0;
}

inline void dec(int &x, int y)
{
	x -= y;
	x < 0 ? x += mod : 0;
}

using std::vector;
vector<int> v[N];
int stk[N], cnt[N], tl[N], tr[N], l[N], r[N], b[N];

int main()
{
	read(T_data);
	while (T_data--)
	{
		read(n); read(ys);
		bm = 0;
		for (int i = 1, x, y; i <= n; ++i)
		{
			read(x); read(y);
			y = Abs(y - ys);
			v[x].emplace_back(y);
			b[++bm] = x;
		}
		std::sort(b + 1, b + bm + 1);
		bm = std::unique(b + 1, b + bm + 1) - b - 1;
		
		int add_tag = 0, coll = 0;
		for (int i = 1; i <= bm; ++i)
		{
			if (i > 1)
				add_tag += b[i] - b[i - 1]; 
			for (int e : v[b[i]])
				++cnt[stk[++top] = e - add_tag + lim];
			l[i] = coll;
			for (int e : v[b[i]])
				if (cnt[e - add_tag + lim] > 1)
				{
					coll += cnt[e - add_tag + lim];
					cnt[e - add_tag + lim] = 0;
				}
			tl[i] = coll;
		}
		while (top)
			cnt[stk[top--]] = 0;
		add_tag = 0, coll = 0;
		for (int i = bm; i >= 1; --i)
		{
			if (i < bm)
				add_tag += b[i + 1] - b[i];
			for (int e : v[b[i]])
				++cnt[stk[++top] = e - add_tag + lim];
			r[i] = coll;
			for (int e : v[b[i]])
				if (cnt[e - add_tag + lim] > 1)
				{
					coll += cnt[e - add_tag + lim];
					cnt[e - add_tag + lim] = 0;
				}
			tr[i] = coll;
		}
		while (top)
			cnt[stk[top--]] = 0;
			
		int maxv = 0, minv = Maxn;
		for (int i = 1; i <= bm; ++i)
		{
			CkMax(maxv, n - l[i] - r[i]);
			CkMin(minv, n - l[i] - r[i]);
			if (i < bm && b[i] + 1 < b[i + 1])
			{
				CkMax(maxv, n - tl[i] - tr[i + 1]);
				CkMin(minv, n - tl[i] - tr[i + 1]); 
			}
		}
		CkMax(maxv, n - tl[n]);
		CkMax(maxv, n - tr[1]);
		CkMin(minv, n - tl[n]);
		CkMin(minv, n - tr[1]);
		
		for (int i = 1; i <= bm; ++i)
			v[b[i]].clear();
//		puts("???");
		put(minv), putchar(' '), put(maxv), putchar('\n'); 
	}
	return 0;
}
/*
1
3 3
2 1
2 5
4 3
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 11856kb

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: 130ms
memory: 17172kb

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
3 9
2 6
3 10
. 2
4 4
2 2
4 4
4 9
4 4
9 9
4 6
0 7
2 8
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 7
1 10
2 2
1 1
, 5
4 9
3 10
1 1
0 7
5 5
0 3
2 2
1 9
1 1
4 8
2 4
2 8
1 4
2 9
. 4
9 9
0 9
1 1
3 8
2 2
2 2
9 9
3 9
4 4
4 6
2 5
0 2
3 5
. 3
0 10
4 4
2 4
2 2
3 6
6 6
6 6
0 2
2 6
0 4
2 6
2 ...

result:

wrong answer 5th numbers differ - expected: '1', found: '3'