QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #163041 | #7105. Pixel Art | ucup-team228 | Compile Error | / | / | C++20 | 7.4kb | 2023-09-03 19:18:19 | 2023-09-03 19:18:20 |
Judging History
你现在查看的是最新测评结果
- [2023-09-04 04:30:22]
- hack成功，自动添加数据
- (//qoj.ac/hack/364)
- [2023-09-03 19:18:20]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-09-03 19:18:19]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSU {
static const int N = 1e6 + 10;
int Parent[N], Rank[N], Size[N], cnt;
void init(int n) {
for (int i = 1; i <= n; i++) {
Parent[i] = i, Rank[i] = 0, Size[i] = 1;
}
cnt = n;
}
int find(int v) {
if (Parent[v] == v) return v;
else return Parent[v] = find(Parent[v]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (Rank[u] < Rank[v]) swap(u, v);
if (Rank[v] == Rank[u]) Rank[u]++;
Parent[v] = u, cnt--;
Size[u] += Size[v];
}
};
DSU dsu;
const int N = 5e5 + 10;
int r1[N], c1[N], r2[N], c2[N];
bool dead[N];
vector<pair<int, int>> row[N], col[N];
set<pair<int, int>> col_lef[N], col_rig[N];
vector<int> open[N], close[N];
ll cnt_black[N];
void init(int n, int m, int k) {
for (int i = 0; i <= n + 1; i++) {
row[i].clear();
open[i].clear();
close[i].clear();
cnt_black[i] = 0;
}
for (int j = 0; j <= m + 1; j++) {
col[j].clear();
col_lef[j].clear();
col_rig[j].clear();
}
for (int i = 1; i <= k; i++) {
dead[i] = false;
}
}
void merge(int n, int m, int k) {
for (int i = 1; i <= k; i++) {
if (dead[i]) {
continue;
} else if (r1[i] == r2[i]) {
row[r1[i]].emplace_back(c1[i], i);
} else {
col[c1[i]].emplace_back(r1[i], i);
}
}
for (int i = 1; i <= n; i++) {
sort(row[i].begin(), row[i].end());
for (int j = int(row[i].size()) - 1; j >= 1; j--) {
int x = row[i][j - 1].second;
int y = row[i][j].second;
if (c2[x] + 1 == c1[y]) {
dead[y] = true;
c2[x] = c2[y];
}
}
}
for (int j = 1; j <= m; j++) {
sort(col[j].begin(), col[j].end());
for (int i = int(col[j].size()) - 1; i >= 1; i--) {
int x = col[j][i - 1].second;
int y = col[j][i].second;
if (r2[x] + 1 == r1[y]) {
dead[y] = true;
r2[x] = r2[y];
}
}
}
}
bool check(int i, int j) {
return max(c1[i], c1[j]) <= min(c2[i], c2[j]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
init(n, m, k);
for (int i = 1; i <= k; i++) {
cin >> r1[i] >> c1[i] >> r2[i] >> c2[i];
}
for (int i = 1; i <= k; i++) {
if (!dead[i] && r1[i] == r2[i]) {
col_lef[c1[i]].emplace(r1[i], i);
col_rig[c2[i]].emplace(r1[i], i);
}
}
for (int i = 1; i <= k; i++) {
if (!dead[i] && r1[i] < r2[i]) {
auto lef = col_rig[c1[i] - 1].lower_bound({r1[i], 0});
auto rig = col_lef[c1[i] + 1].lower_bound({r1[i], 0});
bool ok_lef = lef != col_rig[c1[i] - 1].end() && lef->first <= r2[i];
bool ok_rig = rig != col_lef[c1[i] + 1].end() && rig->first <= r2[i];
if (ok_lef) {
if (ok_rig) {
if (lef->first <= rig->first) {
int j = lef->second;
col_rig[c2[j]].erase({r1[j], j});
c2[j] = c1[i];
col_rig[c2[j]].emplace(r1[j], j);
k++;
dead[k] = false;
r1[k] = r1[j] + 1;
r2[k] = r2[i];
c1[k] = c1[i];
c2[k] = c2[i];
r2[i] = r1[j] - 1;
} else {
int j = rig->second;
col_lef[c1[j]].erase({r1[j], j});
c1[j] = c1[i];
col_rig[c1[j]].emplace(r1[j], j);
k++;
dead[k] = false;
r1[k] = r1[j] + 1;
r2[k] = r2[i];
c1[k] = c1[i];
c2[k] = c1[i];
r2[i] = r1[j] - 1;
}
} else {
int j = lef->second;
col_rig[c2[j]].erase({r1[j], j});
c2[j] = c1[i];
col_rig[c2[j]].emplace(r1[j], j);
k++;
dead[k] = false;
r1[k] = r1[j] + 1;
r2[k] = r2[i];
c1[k] = c1[i];
c2[k] = c2[i];
r2[i] = r1[j] - 1;
}
} else if (ok_rig) {
int j = rig->second;
col_lef[c1[j]].erase({r1[j], j});
c1[j] = c1[i];
col_rig[c1[j]].emplace(r1[j], j);
k++;
dead[k] = false;
r1[k] = r1[j] + 1;
r2[k] = r2[i];
c1[k] = c1[i];
c2[k] = c1[i];
r2[i] = r1[j] - 1;
}
if (r2[i] < r1[i]) {
dead[i] = true;
}
}
}
merge(n, m, k);
/*
for (int i = 1; i <= k; i++) {
if (!dead[i]) {
cout << r1[i] << " " << c1[i] << " " << r2[i] << " " << c2[i] << "\n";
}
}
cout << "\n";
*/
for (int i = 1; i <= k; i++) {
if (!dead[i]) {
open[r1[i]].push_back(i);
close[r2[i] + 1].push_back(i);
cnt_black[r1[i]] += 1ll * (r2[i] - r1[i] + 1) * (c2[i] - c1[i] + 1);
}
}
for (int i = 1; i <= n; i++) {
cnt_black[i] += cnt_black[i - 1];
}
set<pair<int, int>> cur;
dsu.init(k);
int not_seen = k;
for (int r = 1; r <= n; r++) {
for (int i : open[r]) {
not_seen--;
vector<int> tmp;
while (true) {
auto it = cur.lower_bound({c1[i], 0});
if (it == cur.end() || !check(i, it->second)) {
break;
} else {
int j = it->second;
dsu.unite(i, j);
tmp.push_back(j);
cur.erase({c2[j], j});
}
}
for (int j : tmp) {
cur.insert({c2[j], j});
}
}
for (int i : close[r]) {
cur.erase({c2[i], i});
}
for (int i : open[r]) {
cur.insert({c2[i], i});
}
cout << cnt_black[r] << " " << dsu.cnt - not_seen << "\n";
}
}
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
Details
answer.code:37:29: error: ‘std::vector<int> close [500010]’ redeclared as different kind of entity
37 | vector<int> open[N], close[N];
| ^
In file included from /usr/include/c++/11/bits/atomic_wait.h:44,
from /usr/include/c++/11/bits/atomic_base.h:41,
from /usr/include/c++/11/bits/shared_ptr_atomic.h:33,
from /usr/include/c++/11/memory:78,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:82,
from answer.code:1:
/usr/include/unistd.h:353:12: note: previous declaration ‘int close(int)’
353 | extern int close (int __fd);
| ^~~~~
answer.code: In function ‘void init(int, int, int)’:
answer.code:44:16: warning: pointer to a function used in arithmetic [-Wpointer-arith]
44 | close[i].clear();
| ^
answer.code:44:18: error: request for member ‘clear’ in ‘*(close + ((sizetype)i))’, which is of non-class type ‘int(int)’
44 | close[i].clear();
| ^~~~~
answer.code: In function ‘int main()’:
answer.code:194:32: warning: pointer to a function used in arithmetic [-Wpointer-arith]
194 | close[r2[i] + 1].push_back(i);
| ^
cc1plus: warning: pointer to a function used in arithmetic [-Wpointer-arith]
answer.code:194:34: error: request for member ‘push_back’ in ‘*(close + (((sizetype)r2[i]) + 1))’, which is of non-class type ‘int(int)’
194 | close[r2[i] + 1].push_back(i);
| ^~~~~~~~~
answer.code:223:33: warning: pointer to a function used in arithmetic [-Wpointer-arith]
223 | for (int i : close[r]) {
| ^
answer.code:223:33: error: ‘begin’ was not declared in this scope
answer.code:223:33: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
from answer.code:1:
/usr/include/c++/11/valarray:1224:5: note: ‘std::begin’
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
In file included from /usr/include/c++/11/bits/stl_iterator_base_types.h:71,
from /usr/include/c++/11/bits/stl_algobase.h:65,
from /usr/include/c++/11/bits/specfun.h:45,
from /usr/include/c++/11/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from answer.code:1:
/usr/include/c++/11/bits/iterator_concepts.h:943:10: note: ‘std::__detail::begin’
943 | void begin(const auto&) = delete;
| ^~~~~
In file included from /usr/include/c++/11/string_view:44,
from /usr/include/c++/11/bits/basic_string.h:48,
from /usr/include/c++/11/string:55,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/bits/ranges_base.h:562:44: note: ‘std::ranges::__cust::begin’
562 | inline constexpr __cust_access::_Begin begin{};
| ^~~~~
In file included from /usr/include/c++/11/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:129,
from answer.code:1:
/usr/include/c++/11/bits/fs_dir.h:549:3: note: ‘std::filesystem::__cxx11::begin’
549 | begin(recursive_directory_iterator __iter) noexcept
| ^~~~~
answer.code:223:33: error: ‘end’ was not declared in this scope
223 | for (int i : close[r]) {
| ^
answer.code:223:33: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
from answer.code:1:
/usr/include/c++/11/valarray:1244:5: note: ‘std::end’
1244 | end(const valarray<_Tp>& __va)
| ^~~
In file included from /usr/include/c++/11/string_view:44,
from /usr/include/c++/11/bits/basic_string.h:48,
from /usr/include/c++/11/string:55,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
...