QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#588403 | #7105. Pixel Art | Tomorrow | WA | 393ms | 15428kb | C++17 | 3.3kb | 2024-09-25 10:38:08 | 2024-09-25 11:41:45 |
Judging History
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'