oj.uz

Submission #153609

# Submission time Handle Problem Language Result Execution time Memory
153609 2019-09-15T01:16:34 Z myungwoo Rectangles (IOI19_rect) C++14
10 / 100
 5000 ms 921640 KB 
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;

#define fr first
#define sc second
#define sz(v) ((int)(v).size())
typedef long long lld;
typedef pair<int, int> pii;

int N, M;
int A[2502][2502];
pii ver[2502][2502], hor[2502][2502];
map <int, int> verDP[2502][2502], horDP[2502][2502];

inline int get(map<int, int> &m, int x)
{
	auto it = m.find(x);
	return it == m.end() ? 0 : it->second;
}

lld count_rectangles(vector<vector<int>> a)
{
	N = sz(a); M = sz(a[0]);
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) A[i][j] = a[i-1][j-1];
	for (int i=1;i<=N;i++){
		stack <int> stk;
		for (int j=1;j<=M;j++){
			while (!stk.empty() && A[i][stk.top()] <= A[i][j]) stk.pop();
			hor[i][j].fr = stk.empty() ? 1 : stk.top()+1;
			stk.push(j);
		}
		stk = {};
		for (int j=M;j;j--){
			while (!stk.empty() && A[i][stk.top()] <= A[i][j]) stk.pop();
			hor[i][j].sc = stk.empty() ? M : stk.top()-1;
			stk.push(j);
		}
	}
	for (int j=1;j<=M;j++){
		stack <int> stk;
		for (int i=1;i<=N;i++){
			while (!stk.empty() && A[stk.top()][j] <= A[i][j]) stk.pop();
			ver[i][j].fr = stk.empty() ? 1 : stk.top()+1;
			stk.push(i);
		}
		stk = {};
		for (int i=N;i;i--){
			while (!stk.empty() && A[stk.top()][j] <= A[i][j]) stk.pop();
			ver[i][j].sc = stk.empty() ? N : stk.top()-1;
			stk.push(i);
		}
	}
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
		{
			const auto &sg = ver[i][j];
			verDP[sg.fr][sg.sc][j] = get(verDP[sg.fr][sg.sc], j-1)+1;
		}
		{
			const auto &sg = hor[i][j];
			horDP[sg.fr][sg.sc][i] = get(horDP[sg.fr][sg.sc], i-1)+1;
		}
	}
	set <lld> vis;
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
		int sy = ver[i][j].fr, ey = ver[i][j].sc;
		int sx = hor[i][j].fr, ex = hor[i][j].sc;
		if (sy == 1 || ey == N || sx == 1 || ex == M) continue;
		if (get(verDP[sy][ey], ex) <= ex-sx || get(horDP[sx][ex], ey) <= ey-sy) continue;
		lld v = ((sy-1)*M+sx-1)*N*M + (ey-1)*M+ex-1;
		if (vis.count(v)) continue;
		vis.insert(v);
	}
	return sz(vis);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 588588 KB Output is correct
2 Correct 542 ms 588896 KB Output is correct
3 Correct 539 ms 588864 KB Output is correct
4 Correct 537 ms 588872 KB Output is correct
5 Correct 534 ms 588816 KB Output is correct
6 Incorrect 539 ms 588900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 588588 KB Output is correct
2 Correct 542 ms 588896 KB Output is correct
3 Correct 539 ms 588864 KB Output is correct
4 Correct 537 ms 588872 KB Output is correct
5 Correct 534 ms 588816 KB Output is correct
6 Incorrect 539 ms 588900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 588588 KB Output is correct
2 Correct 542 ms 588896 KB Output is correct
3 Correct 539 ms 588864 KB Output is correct
4 Correct 537 ms 588872 KB Output is correct
5 Correct 534 ms 588816 KB Output is correct
6 Incorrect 539 ms 588900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 588588 KB Output is correct
2 Correct 542 ms 588896 KB Output is correct
3 Correct 539 ms 588864 KB Output is correct
4 Correct 537 ms 588872 KB Output is correct
5 Correct 534 ms 588816 KB Output is correct
6 Incorrect 539 ms 588900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 589524 KB Output is correct
2 Correct 546 ms 589300 KB Output is correct
3 Correct 539 ms 588728 KB Output is correct
4 Correct 536 ms 588408 KB Output is correct
5 Correct 543 ms 589364 KB Output is correct
6 Correct 552 ms 589392 KB Output is correct
7 Correct 560 ms 589304 KB Output is correct
8 Correct 543 ms 589364 KB Output is correct
9 Correct 543 ms 589476 KB Output is correct
10 Correct 549 ms 588760 KB Output is correct
11 Correct 609 ms 589052 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 588756 KB Output is correct
2 Correct 2757 ms 750024 KB Output is correct
3 Execution timed out 5132 ms 921640 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 588588 KB Output is correct
2 Correct 542 ms 588896 KB Output is correct
3 Correct 539 ms 588864 KB Output is correct
4 Correct 537 ms 588872 KB Output is correct
5 Correct 534 ms 588816 KB Output is correct
6 Incorrect 539 ms 588900 KB Output isn't correct
7 Halted 0 ms 0 KB -