oj.uz

답안 #171200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171200 2019-12-27T18:18:56 Z nobik Rectangles (IOI19_rect) C++14
10 / 100
 6 ms 1016 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int>>> CalcSegments(const vector<int>& a) {
	int n = static_cast<int>(a.size());
	vector<vector<pair<int, int>>> segments(n);
	vector<int> s;
	for (int i = 0; i < n; ++i) {
		while (!s.empty()) {
			int segment = i - s.back() - 1;
			if (segment > 0) 
				segments[i].emplace_back(segment, 1);
			if (a[s.back()] >= a[i]) 
				break;
			s.pop_back();
		}

		if (!s.empty() && a[s.back()] == a[i])
			s.pop_back();

		s.push_back(i);
	}

	segments.shrink_to_fit();
	return segments;
}

vector<pair<int, int>> Merge(const vector<pair<int, int>>& a, const vector<pair<int, int>>& b) {
	vector<pair<int, int>> r;
	int a_size = static_cast<int>(a.size());
	int j = 0;
	for (const auto& e: b) {
		while (j < a_size && a[j].first < e.first) {
			++j;
		}

		int cnt = e.second;
		if (j < a_size && a[j].first == e.first) {
			cnt += a[j].second;
		}

		r.emplace_back(e.first, cnt);
	}

	return r;
}

struct Fenwick {
	int n;
	vector<int> f;

	Fenwick(int n): n(n), f(n + 1) {}

	void Add(int pos) {
		for (int i = pos + 1; i <= n; i += i & -i) {
			++f[i];
		}
	}

	int Sum(int pos) {
		int r = 0;
		for (int i = pos + 1; i > 0; i -= i & -i) {
			r += f[i];
		}

		return r;
	}
};

int Count(vector<pair<int, int>> a, vector<pair<int, int>> b) {
	if (a.empty() || b.empty()) return 0;
	sort(a.begin(), a.end(), [&](const pair<int, int>& x, const pair<int, int>& y) {
		return x.second < y.second;
	});

	vector<int> cmp;
	for (auto& e: b) {
		cmp.push_back(e.second);
	}

	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
	Fenwick f(cmp.size());

	int b_size = static_cast<int>(b.size());
	int j = 0;

	int r = 0;
	for (auto& e: a) {
		while (j < b_size && b[j].first <= e.second) {
			int y = lower_bound(cmp.begin(), cmp.end(), b[j].second) - cmp.begin();
			f.Add(y);
			++j;
		}

		int pos = lower_bound(cmp.begin(), cmp.end(), e.first) - cmp.begin() - 1;
		r += j - f.Sum(pos);
	}

	return r;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = static_cast<int>(a.size());
	int m = static_cast<int>(a.front().size());

	vector<vector<vector<pair<int, int>>>> horizontal_segments(n, vector<vector<pair<int, int>>>(m));
	vector<vector<vector<pair<int, int>>>> vertical_segments(n, vector<vector<pair<int, int>>>(m));

	for (int i = 0; i < n; ++i) {
		horizontal_segments[i] = CalcSegments(a[i]);
	}

	for (int j = 0; j < m; ++j) {
		vector<int> b;
		for (int i = 0; i < n; ++i) {
			b.push_back(a[i][j]);
		}

		auto segments = CalcSegments(b);
		for (int i = 0; i < n; ++i) {
			vertical_segments[i][j] = segments[i];
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i > 0) horizontal_segments[i][j] = Merge(horizontal_segments[i - 1][j], horizontal_segments[i][j]);
			if (j > 0) vertical_segments[i][j] = Merge(vertical_segments[i][j - 1], vertical_segments[i][j]);
		}
	}

	long long result = 0;
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			/* for (auto& x: horizontal_segments[i - 1][j]) {
				for (auto& y: vertical_segments[i][j - 1]) {
					if (x.first <= y.second && y.first <= x.second)
						++result;
				}
			} */

			result += Count(horizontal_segments[i - 1][j], vertical_segments[i][j - 1]);
		}
	}

	/* for (int i = 1; i < n; ++i) {
		for (int j = 1; j < m; ++j) {
			cout << i << ' ' << j << ": " << endl;
			cout << "HORIZONTAL: "; for (auto& x: horizontal_segments[i - 1][j]) cout << x.first << ' '; cout << endl;
			cout << "VERTICAL: "; for (auto& x: vertical_segments[i][j - 1]) cout << x.first << ' '; cout << endl;
		}
	} */

	return result;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Runtime error 5 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Runtime error 5 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Runtime error 5 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Runtime error 5 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1016 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 5 ms 892 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 5 ms 888 KB Output is correct
9 Correct 6 ms 888 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 4 ms 760 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Runtime error 5 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -