oj.uz

Submission #299224

# Submission time Handle Problem Language Result Execution time Memory
299224 2020-09-14T15:06:34 Z antimirage Rectangles (IOI19_rect) C++14
0 / 100
 457 ms 311276 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (int)7e6 + 7;

struct DSU {
	int par[N], sz[N];
	int mnx[N], mxx[N], mny[N], mxy[N];
	int sum[N];
	DSU() {
		fill(sz, sz + N, 1);
		iota(par, par + N, 0);
	}
	int getpar(int a) {
		return (par[a] == a) ? a : par[a] = getpar(par[a]);
	}
	void connect(int a, int b) {
		a = getpar(a);
		b = getpar(b);
		if (a != b) {
			if (sz[a] > sz[b]) swap(a, b);
			sz[b] += sz[a];
			par[a] = b;
			mnx[b] = min(mnx[b], mnx[a]);
			mxx[b] = max(mxx[b], mxx[a]);
			mny[b] = min(mny[b], mny[a]);
			mxy[b] = max(mxy[b], mxy[a]);
			sum[b] += sum[a];
		}
	}
}dsu;

int n, m;

int getpos(int x, int y) {
	return x * m + y;
}

vector <int> vec[N];

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dsu.mnx[getpos(i, j)] = dsu.mxx[getpos(i, j)] = i;
			dsu.mny[getpos(i, j)] = dsu.mxy[getpos(i, j)] = j;
			dsu.sum[getpos(i, j)] = 4;
			if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
				dsu.sum[getpos(i, j)] = 1e5;
			}
			vec[a[i][j]].push_back(getpos(i, j));
		}
	}
	long long ans = 0;
	for (int i = 0; i < N; i++) {
		if (vec[i].empty()) continue;
		int res = 0;
		for (int to : vec[i]) {
			if (to % m != 0) { // y - 1
				if (a[to / m][to % m - 1] < i) {
					dsu.connect(to, to - 1);
					res++;
				} else {
					dsu.sum[to - 1]--;
				}
			} 
			if (to % m != m - 1) { // y + 1
				if (a[to / m][to % m + 1] < i) {
					dsu.connect(to, to + 1);
					res++;
				} else {
					dsu.sum[to + 1]--;
				}
			}
			if (to / m > 0) { // x - m
				if (a[to / m - 1][to % m] < i) {
					dsu.connect(to, to - m);
					res++;
				} else {
					dsu.sum[to - m]--;
				}
			}	
			if (to / m < n - 1) { // x + m
				if (a[to / m + 1][to % m] < i) {
					dsu.connect(to, to + m);
					res++;
				} else {
					dsu.sum[to + m]--;
				}
			}
			dsu.sum[dsu.getpar(to)] -= res;
		}
		for (int to : vec[i]) {
			int par = dsu.getpar(to);
			int sum = dsu.sum[par];
			int need = ((dsu.mxx[par] - dsu.mnx[par] + 1) + (dsu.mxy[par] - dsu.mny[par] + 1)) * 2;
			int area = (dsu.mxx[par] - dsu.mnx[par] + 1) * (dsu.mxy[par] - dsu.mny[par] + 1);
			if (sum == need && dsu.sz[par] == area) {
				ans++;
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 219476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 219476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 219476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 219476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 220024 KB Output is correct
2 Correct 164 ms 219896 KB Output is correct
3 Correct 164 ms 219896 KB Output is correct
4 Correct 161 ms 219592 KB Output is correct
5 Incorrect 168 ms 220152 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 219640 KB Output is correct
2 Incorrect 457 ms 311276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 219476 KB Output isn't correct
2 Halted 0 ms 0 KB -