QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#588403#7105. Pixel ArtTomorrowWA 393ms15428kbC++173.3kb2024-09-25 10:38:082024-09-25 11:41:45

Judging History

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

  • [2024-09-25 11:41:45]
  • 评测
  • 测评结果:WA
  • 用时:393ms
  • 内存:15428kb
  • [2024-09-25 10:38:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define C const
#define U unsigned
#define SC static
#define CE constexpr
#define TL template
#define TN typename
#define OP operator
#define pb push_back
#define ft first
#define sd second
#define mi (l + (r - l) / 2)
#define TTT TL<TN T = I>
#define TTI TL<TN It>
#define BE(v) v.begin(), v.end()
#define VD void
#define BL bool
#define CH char
#define I int
#define LL long long
#define II __int128
#define D double
using PII = pair<I, I>;
TTT using V = vector<T>;

#define FORX(v) for(auto& x : v)
#define FOR(i, b, e)  for(auto i = b, _e = (decltype(i))e;i != _e; ++i)
#define FORR(i, b, e) for(auto i = b, _e = (decltype(i))e;i != _e; --i)
#define FORV(v, i) for (I i = 0, _n = v.size(), x = _n ? v[0] : 0;i < _n;x = v[++i])
#define FUNC(T, f, ...) function<T(__VA_ARGS__)> f = [&](__VA_ARGS__)->T

#define DR(T, ...) T __VA_ARGS__; R(__VA_ARGS__);
TTT VD R(T& x) { cin >> x; }
TTT T R() { DR(T, x); return x; }
TL<TN T, TN... A> VD R(T& x, A&... a) { R(x), R(a...); }
CE CH LF = '\n', SP = ' ';
TL<CH s = LF> VD W() { cout << s; }
TL<CH s = LF, TN T> VD W(C T& x) { cout << x << s; }
TL<CH s = LF, TN T, TN... A> VD W(C T& x, C A&... a) { W<SP>(x), W<s>(a...); }

TTT CE T inf() { return numeric_limits<T>::max() / 2; }
TTT VD setmin(T& a, C T& b) { if (b < a)a = b; }
TTT VD setmax(T& a, C T& b) { if (a < b)a = b; }

struct DSU
{
	V<I> f;
	DSU(I n) :f(n) { FOR(i, 0, n)f[i] = i; }
	I fa(I p) { return p == f[p] ? p : (f[p] = fa(f[p])); }
	BL merge(I x, I y) { f[y = fa(y)] = x = fa(x);return x != y; }
};
struct P
{
	I l, r, id;
	friend BL OP < (C P& a, C P& b) { return a.r < b.l; }
};
VD test()
{
	DR(I, n, m, k); ++n;
	using PP = pair<I, PII>;
	V<V<PII>> v(n + 1); V<multiset<P>> h(n);
	map<I, I> vm; LL tot = 0, cnt = 0;
	FOR(i, 0, k)
	{
		DR(I, r1, c1, r2, c2);
		if (r1 == r2)h[r1].insert({ c1,c2,i });
		else v[r1].pb({ c1,i }), v[r2 + 1].pb({ c1,i });
	}
	DSU ds(k);
	FOR(i, 1, n)
	{
		FORX(v[i])
		{
			I r = x.ft, id = x.sd;
			if (vm.count(r) && vm[r] == id)
			{
				vm.erase(r);
				if (h[i].count({ r,r }))cnt -= ds.merge(h[i].find({ r,r })->id, id);//6
			}
			else
			{
				if (vm.count(r))cnt -= ds.merge(vm[r], id);//1
				++cnt; vm[r] = id;
				if (h[i - 1].count({ r,r }))cnt -= ds.merge(h[i - 1].find({ r,r })->id, id);//7
			}
		}
		FORX(v[i])
		{
			I r = x.ft, id = x.sd;
			if (!vm.count(r))continue;
			if (vm.count(r - 1))cnt -= ds.merge(vm[r - 1], id);//2
			if (vm.count(r + 1))cnt -= ds.merge(vm[r + 1], id);//3
		}
		tot += vm.size();
		FOR(it, h[i].begin(), h[i].end())
		{
			auto& x = *it; tot += x.r - x.l + 1; ++cnt;
			for (auto& y : h[i - 1])if (!(x < y || y < x))cnt -= ds.merge(y.id, x.id);
			// auto er = h[i - 1].equal_range(x);
			// for (auto ii = er.ft; ii != er.sd;++ii)cnt -= ds.merge(ii->id, x.id);//4
			auto ir = it; if (++ir != _e && x.r + 1 == ir->l)cnt -= ds.merge(ir->id, x.id);//5
			if (vm.count(x.l - 1))cnt -= ds.merge(vm[x.l - 1], x.id);//8
			if (vm.count(x.r + 1))cnt -= ds.merge(vm[x.r + 1], x.id);//9
		}
		W(tot, cnt);
	}
}

I main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	if (fopen("test.in", "r"))
	{
		freopen("test.in", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	I t = 1;
	R(t);
	while (t--)test();
	return 0;
}

詳細信息

Test #1:

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

input:

3
2 5 2
1 1 1 2
2 3 2 5
2 5 2
1 1 1 3
2 3 2 5
3 3 3
1 1 1 2
3 1 3 2
1 3 2 3

output:

2 1
5 2
3 1
6 1
3 1
4 1
6 2

result:

ok 7 lines

Test #2:

score: -100
Wrong Answer
time: 393ms
memory: 15428kb

input:

2130
2 5 2
1 1 1 2
2 3 2 5
2 5 2
1 1 1 3
2 3 2 5
3 3 3
1 1 1 2
3 1 3 2
1 3 2 3
3 100 51
1 2 2 2
1 4 2 4
1 6 2 6
1 8 2 8
1 10 2 10
1 12 2 12
1 14 2 14
1 16 2 16
1 18 2 18
1 20 2 20
1 22 2 22
1 24 2 24
1 26 2 26
1 28 2 28
1 30 2 30
1 32 2 32
1 34 2 34
1 36 2 36
1 38 2 38
1 40 2 40
1 42 2 42
1 44 2 44
...

output:

2 1
5 2
3 1
6 1
3 1
4 1
6 2
50 50
100 50
200 1
50 50
150 1
200 1
2 1
4 1
6 1
8 1
10 1
12 1
14 1
16 1
18 1
20 1
22 1
24 1
26 1
28 1
30 1
32 1
34 1
36 1
38 1
40 1
42 1
44 1
46 1
48 1
50 1
52 1
54 1
56 1
58 1
60 1
62 1
64 1
66 1
68 1
70 1
72 1
74 1
76 1
78 1
80 1
82 1
84 1
86 1
88 1
90 1
92 1
94 1
96 1...

result:

wrong answer 10129th lines differ - expected: '6 2', found: '6 4'