oj.uz

Submission #1031007

# Submission time Handle Problem Language Result Execution time Memory
1031007 2024-07-22T13:26:32 Z fv3 Rectangles (IOI19_rect) C++14
0 / 100
 5000 ms 82404 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N, M;
vector<vector<int>> grid;

struct node
{
	int n = 0;
};
node merge(node a, node b)
{
	return {max(a.n, b.n)};
}
node emptyNode = {0};

vector<vector<node>> st_v, st_h;
int nt_v = 1, nt_h = 1;

node v_range(int l, int r, int k, int x, int y, int i)
{
	if (y < l || x > r) return emptyNode;
	if (x >= l && y <= r) return st_v[i][k];
	int c = (x + y) / 2;
	return merge(v_range(l, r, k*2, x, c, i), v_range(l, r, k*2|1, c+1, y, i));
}

node h_range(int l, int r, int k, int x, int y, int i)
{
	if (y < l || x > r) return emptyNode;
	if (x >= l && y <= r) return st_h[i][k];
	int c = (x + y) / 2;
	return merge(h_range(l, r, k*2, x, c, i), h_range(l, r, k*2|1, c+1, y, i));
}

ll count_rectangles(vector<vector<int>> a) 
{
	N = a.size();
	M = a[0].size();

	// Construct horizontal segment trees
	while (nt_h < M) nt_h <<= 1;
	for (int i = 0; i < N; i++)
	{
		st_h.push_back(vector<node>(2 * nt_h));
		for (int j = 0; j < M; j++)
			st_h[i][nt_h + j].n = a[i][j];

		for (int j = nt_h - 1; j >= 1; j--)
			st_h[i][j] = merge(st_h[i][j*2], st_h[i][j*2|1]); 
	}

	// Construct vertical segment trees
	while (nt_v < N) nt_v <<= 1;
	for (int i = 0; i < N; i++)
	{
		st_v.push_back(vector<node>(2 * nt_v));
		for (int j = 0; j < N; j++)
			st_v[i][nt_v + j].n = a[j][i];

		for (int j = nt_v - 1; j >= 1; j--)
			st_v[i][j] = merge(st_v[i][j*2], st_v[i][j*2|1]); 
	}

	set<ll> sv, sh;

	for (int x1 = 1; x1 < M - 1; x1++)
	{
		for (int x2 = x1; x2 < M - 1; x2++)
		{
			for (int y1 = 1; y1 < N - 1; y1++)
			{
				for (int y2 = y1; y2 < N - 1; y2++)
				{
					if (h_range(x1, x2, 1, 0, nt_h - 1, y2).n >= min(a[y2][x1-1], a[y2][x2+1])) 
						break;

					//cerr << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';

					sh.insert(x1*15625000000ll+x2*6250000ll+y1*2500+y2);
				}
			}
		}
	}

	//cerr << '\n';

	ll res = 0;
	for (int y1 = 1; y1 < N - 1; y1++)
	{
		for (int y2 = y1; y2 < N - 1; y2++)
		{
			for (int x1 = 1; x1 < M - 1; x1++)
			{
				for (int x2 = x1; x2 < M - 1; x2++)
				{
					if (v_range(y1, y2, 1, 0, nt_v - 1, x2).n >= min(a[y1-1][x2], a[y2+1][x2])) 
						break;

					//cerr << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2;
					//cout << y1 << ' ' << y2 << ' ' << x2 << " = " << v_range(y1, y2, 1, 0, nt_v - 1, x2).n << '\n';
					if (sh.count(x1*15625000000ll+x2*6250000ll+y1*2500+y2))
					{
						res++;
						//cerr << " <--";
					}
					//cerr << '\n';
				}
			}
		}
	}

	//cerr << '\n';



	return res;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 311 ms 828 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 5045 ms 82404 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -