oj.uz

Submission #261399

# Submission time Handle Problem Language Result Execution time Memory
261399 2020-08-11T17:12:25 Z SuperJava Rectangles (IOI19_rect) C++17
0 / 100
 117 ms 89336 KB 
#include "rect.h"
#include <vector>
#include <cmath>
#include <iostream>
#define sz(a) (a.size())
using namespace std;

int spr[705][11][705];
int spc[705][11][705];
int lg[705];

int query_r(int row, int l, int r){
	int logo = lg[r-l+1];
	return max(spr[row][logo][l],spr[row][logo][r-(1<<logo)+1]);
}

int query_c(int col, int l, int r){
	int logo = lg[r-l+1];
	return max(spc[col][logo][l],spc[col][logo][r-(1<<logo)+1]);
}

long long count_rectangles(vector<vector<int>> a) {
	for (int i = 1; i < 705; ++i){
		lg[i] = log2(i);
	}
	int n = sz(a);
	int m = sz(a[0]);
	int answer = 0;
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j){
			spr[i][0][j] = a[i][j];
		}
		for (int k = 1; k < 11; ++k){
			for (int j = 0; j < n-(1<<k)+1; ++j){
				spr[i][k][j] = max(spr[i][k-1][j], spr[i][k-1][j+(1<<(k-1))]);
			}
		}
	}
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j){
			spc[i][0][j] = a[j][i];
		}
		for (int k = 1; k < 11; ++k){
			for (int j = 0; j < n-(1<<k)+1; ++j){
				spc[i][k][j] = max(spc[i][k-1][j], spc[i][k-1][j+(1<<(k-1))]);
			}
		}
	}
	for (int r1 = 1; r1 < n-1; ++r1){
		for (int c1 = 1; c1 < m-1; ++c1){
			for (int r2 = r1; r2 < n-1; ++r2){
				if(a[r2][c1] >= a[r2][c1-1] ||
					a[r2][c1] >= a[r1-1][c1]){
					break;
				}
				bool milhem = false;
				for (int c2 = c1; c2 < m-1 && !milhem; ++c2){
					bool good = true;
					for (int i = r1; i <= r2 && good; ++i){
						int mx = query_r(i, c1, c2);
						if(mx >= a[i][c1-1]){
							good = false;
							milhem = true;
						}
						if(mx >= a[i][c2+1]){
							good = false;
						}
					}
					for (int i = c1; i <= c2 && good; ++i){
						int mx = query_c(i, r1, r2);
						if(mx >= a[r1-1][i] || mx >= a[r2+1][i]){
							good = false;
							milhem = true;
						}
					}
					if(good){
						answer++;
					}
				}
			}
		}
	}
	return answer;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 2 ms 1280 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Incorrect 1 ms 1280 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 2 ms 1280 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Incorrect 1 ms 1280 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 2 ms 1280 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Incorrect 1 ms 1280 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 2 ms 1280 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Incorrect 1 ms 1280 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Runtime error 117 ms 89336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 2 ms 1280 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Incorrect 1 ms 1280 KB Output isn't correct
8 Halted 0 ms 0 KB -