QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95921 | #6136. Airdrop | CSU2023 | WA | 130ms | 17172kb | C++14 | 3.3kb | 2023-04-12 14:55:00 | 2023-04-12 14:55:03 |
Judging History
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'