QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#162978#7105. Pixel Artucup-team1209AC ✓577ms34060kbC++204.0kb2023-09-03 18:23:282023-09-04 04:31:26

Judging History

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

  • [2023-09-04 04:31:26]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:577ms
  • 内存:34060kb
  • [2023-09-03 18:23:29]
  • 评测
  • 测评结果:100
  • 用时:641ms
  • 内存:34896kb
  • [2023-09-03 18:23:28]
  • 提交

answer

#include<bits/stdc++.h>
#define link lk
using std::cin;
using std::cout;
const int N = 100005;
using ll = long long;
using pr = std::pair<int, int>;
int n, m, k;
pr un(pr x, pr y) {
	pr res(std::min(x.first, y.first), 0);
	if(res.first==x.first)res.second+=x.second;
	if(res.first==y.first)res.second+=y.second;
	return res;
}


int add[N << 2];
pr sgt[N << 2];
void put(int x, int v) {
	add[x] += v;
	sgt[x].first += v;
}
void down(int x) {
	put(x << 1, add[x]);
	put(x << 1 | 1, add[x]);
	add[x] = 0;
}
void update(int x) {
	sgt[x] = un(sgt[x << 1], sgt[x << 1 | 1]);
}
void build(int cur, int l, int r) {
	if(l == r) {
		sgt[cur] = {0, 1};
		return ;
	}
	down(cur);
	int mid = (l + r) >> 1;
	build(cur << 1, l, mid);
	build(cur << 1 | 1, mid + 1, r);
	update(cur);
}
void apply(int ql, int qr, int v, int cur = 1, int l = 1, int r = 1e5) {
	if(ql <= l && r <= qr) {
		put(cur, v);
		return ;
	}
	int mid = (l + r) >> 1;
	down(cur);
	if(ql <= mid) apply(ql, qr, v, cur << 1, l, mid);
	if(mid < qr) apply(ql, qr, v, cur << 1 | 1, mid + 1, r);
	update(cur);
}
struct ds {
	std::vector<std::pair<int, pr>> map;
	void set(int l, int r, int v) {
		map.emplace_back(r, pr(l, v));
	}
	void init() {
		sort(map.begin(), map.end());
	}
	int test(int p) {
		auto iter = lower_bound(map.begin(), map.end(), make_pair(p, pr(0, 0)));
		if(iter == map.end()) return -1;
		if(iter -> second.first <= p) {
			return iter -> second.second;
		}
		return -1;
	}
	void clear() {
		map.clear();
	}
} A[N], B[N];

int anc[N];
int find(int x) {
	return anc[x] == x ? x : anc[x] = find(anc[x]);
}
int un(int x, int y) {
	if(find(x) != find(y)) {
		anc[find(x)] = y;
		return 1;
	}
	return 0;
}
int test(int x, int y) {
	int t = A[x].test(y);
	if(t != -1) return t;
	return B[y].test(x);
}
std::vector<int> a[N];
std::vector<int> b[N];
std::vector<pr> link[N];
int add_[N];
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);

	#ifdef zqj
	freopen("$.in", "r", stdin);
#endif
	int T;
	cin >> T;
		build(1, 1, 1e5);
	for(int i = 0;i < T;++i) {
		cin >> n >> m >> k;
		std::vector<int> r1(k + 1);
		std::vector<int> r2(k + 1);
		std::vector<int> c1(k + 1);
		std::vector<int> c2(k + 1);
		std::vector<int> M(k + 1);
		std::vector<int> Ms;
		for(int i = 1;i <= k;++i) {
			anc[i] = i;
			cin >> r1[i] >> c1[i] >> r2[i] >> c2[i];
			add_[M[i] = std::min(r1[i], r2[i])] += 1;
			Ms.push_back(c1[i]);
			Ms.push_back(c2[i]);
			if(r1[i] == r2[i]) {
				A[r1[i]].set(c1[i], c2[i], i);
				a[r1[i]].push_back(i);
			} else {
				b[r1[i]].push_back(i);
				b[r2[i] + 1].push_back(-i);
				B[c1[i]].set(r1[i], r2[i], i);
			}
		}
		sort(Ms.begin(), Ms.end());
		Ms.erase(unique(Ms.begin(), Ms.end()), Ms.end());
		int dx[4] = {1, -1, 0, 0};
		int dy[4] = {0, 0, 1, -1};
		for(int i = 1;i <= n;++i) {
			A[i].init();
		}
		for(int i : Ms) {
			B[i].init();
		}
		for(int i = 1;i <= k;++i) {
			for(pr x : {pr(r1[i], c1[i]), pr(r2[i], c2[i])}) {
				for(int j = 0;j < 4;++j) {
					int xx = x.first + dx[j];
					int yy = x.second + dy[j];
					if(r1[i] <= xx && xx <= r2[i])
						if(c1[i] <= yy && yy <= c2[i])
							continue;
					int c = test(xx, yy);
					if(c != -1) link[std::max(M[c], M[i])].emplace_back(c, i);
				}
			}
		}
		ll sum = 0;
		int con = 0;
		for(int i = 1;i <= n;++i) {
			con += add_[i];
			for(auto [x, y] : link[i]) {
				con -= un(x, y);
			}
			for(int x : a[i]) apply(c1[x], c2[x], 1);
			for(int x : a[i - 1]) apply(c1[x], c2[x], -1);
			for(int x : b[i]) {
				if(x > 0) {
					apply(c1[x], c1[x], 1);
				} else {
					apply(c1[-x], c1[-x], -1);
				}
			}
			sum += 1e5;
			if(sgt[1].first == 0) sum -= sgt[1].second;
			cout << sum << ' ' << con << '\n';
		}
		for(int x : a[n]) apply(c1[x], c2[x], -1);
		for(int x : b[n + 1]) apply(c1[-x], c1[-x], -1);
		for(int i = 0;i <= n + 1;++i) {
			link[i].clear();
			A[i].clear();
			a[i].clear();
			b[i].clear();
			add_[i] = 0;
		}
		for(int x : Ms) {
			B[x].clear();
		}
	}
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 577ms
memory: 34060kb

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:

ok 355756 lines

Extra Test:

score: 0
Extra Test Passed