QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#175218#7105. Pixel Artmendicillin2#RE 0ms4248kbC++174.9kb2023-09-10 16:50:072023-09-10 16:50:09

Judging History

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

  • [2023-09-10 16:50:09]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:4248kb
  • [2023-09-10 16:50:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
using uint = uint32_t;
using ull = uint64_t;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

template <class F>
struct ycr {
	F f;
	template <class T> explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args> decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F> decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

struct GC {
	char buf[1 << 16];
	size_t s = 0, e = 0;
	char operator()() {
		if (s >= e) {
			buf[0] = 0;
			s = 0;
			e = fread(buf, 1, sizeof(buf), stdin);
		}
		return buf[s++];
	}
} gc;

template <class T> T scan_int() {
	char c;
	while ((c = gc()) < 40);
	if (c == '-') return -scan_int<T>();
	T a = c - '0';
	while (isdigit(c = gc())) a = a * 10 + c - '0';
	return a;
}

int scan() {
	return scan_int<int>();
}

const int MAXM = 1.1e5;
int idx_ver[MAXM];

void solve() {
	int N = scan();
	int M = scan();
	int K = scan();
	struct hor_t {
		int l, r;
		int i;

		bool operator < (const hor_t& o) const {
			return l < o.l;
		}
	};
	struct ver_t {
		int c;
		int i;

		bool operator < (const ver_t& o) const {
			return c < o.c;
		}
	};
	vector<vector<hor_t>> hors(N);
	vector<vector<ver_t>> vers(N+1);
	for (int k = 0; k < K; k++) {
		int r1 = scan()-1;
		int c1 = scan()-1;
		int r2 = scan()-1;
		int c2 = scan()-1;
		if (r1 == r2) {
			hors[r1].push_back({c1, c2, k});
		} else if (c1 == c2) {
			vers[r1].push_back({c1, k});
			vers[r2+1].push_back({~c1, k});
		} else assert(false);
	}

	vector<int> par(K, -1);
	int num_ccs = 0;
	auto getpar = yc([&](auto self, int i) -> int {
		return par[i] < 0 ? i : (par[i] = self(par[i]));
	});
	auto merge = [&](int a, int b) -> void {
		assert(0 <= a && a < K);
		assert(0 <= b && b < K);

		a = getpar(a), b = getpar(b);
		if (a != b) {
			num_ccs--;
			if (par[a] < par[b]) swap(a, b);
			par[a] += par[b];
			par[b] = a;
		}
	};

	ll cur_num = 0;
	int num_vers = 0;
	vector<ver_t> last_row_vers;
	for (int row_num = 0; row_num <= N; row_num++) {
		for (const auto& [c, k] : vers[row_num]) {
			if (c >= 0) {
				idx_ver[c] = k;
				num_ccs++;
				num_vers++;
			} else {
				idx_ver[~c] = -1;
				num_vers--;
			}
		}

		if (row_num == N) {
			break;
		}

		num_ccs += int(hors[row_num].size());

		cur_num += num_vers;
		for (const auto& [l, r, i] : hors[row_num]) {
			cur_num += r-l+1;
		}

		// v-v
		for (auto [c, k] : vers[row_num]) {
			if (c >= 0) {
				if (c-1 >= 0 && idx_ver[c-1] != -1) {
					merge(idx_ver[c-1], idx_ver[c]);
				}
				if (c+1 < M && idx_ver[c+1] != -1) {
					merge(idx_ver[c], idx_ver[c+1]);
				}
			}
		}

		// v-(some h from the last row)
		if (row_num >= 1) {
			auto j = 0;
			for (auto [c, k] : vers[row_num]) {
				if (c >= 0) {
					while (j < int(hors[row_num-1].size()) && hors[row_num-1][j].r < c) {
						j++;
					}
					if (j < int(hors[row_num-1].size()) && hors[row_num-1][j].l <= c) {
						merge(idx_ver[c], hors[row_num-1][j].i);
					}
				}
			}
		}

		sort(hors[row_num].begin(), hors[row_num].end());

		// h-h
		for (int j = 0; j+1 < int(hors[row_num].size()); j++) {
			if (hors[row_num][j].r+1 == hors[row_num][j+1].l) {
				merge(hors[row_num][j].i, hors[row_num][j+1].i);
			}
		}

		// h-(some v to the left/right)
		for (const auto& [l, r, i] : hors[row_num]) {
			if (l-1 >= 0 && idx_ver[l-1] != -1) {
				merge(idx_ver[l-1], i);
			}
			if (r+1 < M && idx_ver[r+1] != -1) {
				merge(i, idx_ver[r+1]);
			}
		}

		// h-(some v from the last row)
		if (row_num >= 1) {
			last_row_vers.clear();
			for (const auto& [c, i] : vers[row_num-1]) {
				if (c < 0) {
					last_row_vers.push_back({~c, i});
				}
			}
			sort(last_row_vers.begin(), last_row_vers.end());
			int st = 0;
			for (const auto& [l, r, i] : hors[row_num]) {
				while (st < int(last_row_vers.size()) && last_row_vers[st].c < l) {
					st++;
				}
				for (int j = st; j < int(last_row_vers.size()); j++) {
					if (last_row_vers[j].c > r) break;
					merge(i, last_row_vers[j].i);
				}
			}
		}

		// h-(some h from the last row)
		if (row_num >= 1) {
			int st = 0;
			for (const auto& [l, r, i] : hors[row_num]) {
				while (st < int(hors[row_num-1].size()) && hors[row_num-1][st].r < l) {
					st++;
				}
				for (int j = st; j < int(hors[row_num-1].size()); j++) {
					if (max(l, hors[row_num-1][j].l) <= min(r, hors[row_num-1][j].r)) {
						merge(i, hors[row_num-1][j].i);
					} else {
						break;
					}
				}
			}
		}

		cout << cur_num << ' ' << num_ccs << '\n';
		//cerr << cur_num << ' ' << num_ccs << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	memset(idx_ver, -1, sizeof(idx_ver));

	int T = scan();
	while (T--) solve();
}

詳細信息

Test #1:

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

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
Dangerous Syscalls

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 51
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 ...

result: