oj.uz

Submission #153610

# Submission time Handle Problem Language Result Execution time Memory
153610 2019-09-15T01:17:38 Z myungwoo Rectangles (IOI19_rect) C++14
37 / 100
 5000 ms 893772 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 j=1;j<=M;j++) for (int i=1;i<=N;i++){
		const auto &sg = ver[i][j];
		verDP[sg.fr][sg.sc][j] = get(verDP[sg.fr][sg.sc], j-1)+1;
	}
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
		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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 588384 KB Output is correct
2 Correct 540 ms 588816 KB Output is correct
3 Correct 545 ms 589020 KB Output is correct
4 Correct 541 ms 588792 KB Output is correct
5 Correct 545 ms 588924 KB Output is correct
6 Correct 536 ms 588828 KB Output is correct
7 Correct 555 ms 588716 KB Output is correct
8 Correct 539 ms 588536 KB Output is correct
9 Correct 537 ms 588792 KB Output is correct
10 Correct 539 ms 588832 KB Output is correct
11 Correct 538 ms 588804 KB Output is correct
12 Correct 543 ms 588892 KB Output is correct
13 Correct 553 ms 588444 KB Output is correct
14 Correct 572 ms 588472 KB Output is correct
15 Correct 599 ms 588504 KB Output is correct
16 Correct 541 ms 588524 KB Output is correct
17 Correct 543 ms 588356 KB Output is correct
18 Correct 550 ms 588312 KB Output is correct
19 Correct 540 ms 588740 KB Output is correct
20 Correct 541 ms 588664 KB Output is correct
21 Correct 539 ms 588476 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 588384 KB Output is correct
2 Correct 540 ms 588816 KB Output is correct
3 Correct 545 ms 589020 KB Output is correct
4 Correct 541 ms 588792 KB Output is correct
5 Correct 545 ms 588924 KB Output is correct
6 Correct 536 ms 588828 KB Output is correct
7 Correct 555 ms 588716 KB Output is correct
8 Correct 539 ms 588536 KB Output is correct
9 Correct 537 ms 588792 KB Output is correct
10 Correct 539 ms 588832 KB Output is correct
11 Correct 538 ms 588804 KB Output is correct
12 Correct 543 ms 588892 KB Output is correct
13 Correct 553 ms 588444 KB Output is correct
14 Correct 572 ms 588472 KB Output is correct
15 Correct 599 ms 588504 KB Output is correct
16 Correct 541 ms 588524 KB Output is correct
17 Correct 557 ms 590388 KB Output is correct
18 Correct 549 ms 590440 KB Output is correct
19 Correct 551 ms 590532 KB Output is correct
20 Correct 544 ms 589816 KB Output is correct
21 Correct 547 ms 590120 KB Output is correct
22 Correct 578 ms 590304 KB Output is correct
23 Correct 545 ms 590200 KB Output is correct
24 Correct 542 ms 589844 KB Output is correct
25 Correct 543 ms 588356 KB Output is correct
26 Correct 550 ms 588312 KB Output is correct
27 Correct 540 ms 588740 KB Output is correct
28 Correct 541 ms 588664 KB Output is correct
29 Correct 539 ms 588476 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 588384 KB Output is correct
2 Correct 540 ms 588816 KB Output is correct
3 Correct 545 ms 589020 KB Output is correct
4 Correct 541 ms 588792 KB Output is correct
5 Correct 545 ms 588924 KB Output is correct
6 Correct 536 ms 588828 KB Output is correct
7 Correct 555 ms 588716 KB Output is correct
8 Correct 539 ms 588536 KB Output is correct
9 Correct 537 ms 588792 KB Output is correct
10 Correct 539 ms 588832 KB Output is correct
11 Correct 538 ms 588804 KB Output is correct
12 Correct 543 ms 588892 KB Output is correct
13 Correct 553 ms 588444 KB Output is correct
14 Correct 572 ms 588472 KB Output is correct
15 Correct 599 ms 588504 KB Output is correct
16 Correct 541 ms 588524 KB Output is correct
17 Correct 557 ms 590388 KB Output is correct
18 Correct 549 ms 590440 KB Output is correct
19 Correct 551 ms 590532 KB Output is correct
20 Correct 544 ms 589816 KB Output is correct
21 Correct 547 ms 590120 KB Output is correct
22 Correct 578 ms 590304 KB Output is correct
23 Correct 545 ms 590200 KB Output is correct
24 Correct 542 ms 589844 KB Output is correct
25 Correct 601 ms 597816 KB Output is correct
26 Correct 586 ms 597668 KB Output is correct
27 Correct 636 ms 597768 KB Output is correct
28 Correct 561 ms 593656 KB Output is correct
29 Correct 580 ms 596344 KB Output is correct
30 Correct 584 ms 596588 KB Output is correct
31 Correct 581 ms 596264 KB Output is correct
32 Correct 572 ms 596156 KB Output is correct
33 Correct 543 ms 588356 KB Output is correct
34 Correct 550 ms 588312 KB Output is correct
35 Correct 540 ms 588740 KB Output is correct
36 Correct 541 ms 588664 KB Output is correct
37 Correct 539 ms 588476 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 588384 KB Output is correct
2 Correct 540 ms 588816 KB Output is correct
3 Correct 545 ms 589020 KB Output is correct
4 Correct 541 ms 588792 KB Output is correct
5 Correct 545 ms 588924 KB Output is correct
6 Correct 536 ms 588828 KB Output is correct
7 Correct 555 ms 588716 KB Output is correct
8 Correct 539 ms 588536 KB Output is correct
9 Correct 537 ms 588792 KB Output is correct
10 Correct 539 ms 588832 KB Output is correct
11 Correct 538 ms 588804 KB Output is correct
12 Correct 543 ms 588892 KB Output is correct
13 Correct 553 ms 588444 KB Output is correct
14 Correct 572 ms 588472 KB Output is correct
15 Correct 599 ms 588504 KB Output is correct
16 Correct 541 ms 588524 KB Output is correct
17 Correct 557 ms 590388 KB Output is correct
18 Correct 549 ms 590440 KB Output is correct
19 Correct 551 ms 590532 KB Output is correct
20 Correct 544 ms 589816 KB Output is correct
21 Correct 547 ms 590120 KB Output is correct
22 Correct 578 ms 590304 KB Output is correct
23 Correct 545 ms 590200 KB Output is correct
24 Correct 542 ms 589844 KB Output is correct
25 Correct 601 ms 597816 KB Output is correct
26 Correct 586 ms 597668 KB Output is correct
27 Correct 636 ms 597768 KB Output is correct
28 Correct 561 ms 593656 KB Output is correct
29 Correct 580 ms 596344 KB Output is correct
30 Correct 584 ms 596588 KB Output is correct
31 Correct 581 ms 596264 KB Output is correct
32 Correct 572 ms 596156 KB Output is correct
33 Correct 877 ms 659456 KB Output is correct
34 Correct 903 ms 659428 KB Output is correct
35 Correct 896 ms 659392 KB Output is correct
36 Correct 979 ms 659432 KB Output is correct
37 Correct 1236 ms 682448 KB Output is correct
38 Correct 1252 ms 682488 KB Output is correct
39 Correct 1252 ms 682732 KB Output is correct
40 Correct 1222 ms 676752 KB Output is correct
41 Correct 791 ms 623736 KB Output is correct
42 Correct 944 ms 631528 KB Output is correct
43 Correct 1468 ms 665332 KB Output is correct
44 Correct 1471 ms 667900 KB Output is correct
45 Correct 927 ms 632440 KB Output is correct
46 Correct 914 ms 628068 KB Output is correct
47 Incorrect 1509 ms 663336 KB Output isn't correct
48 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 589416 KB Output is correct
2 Correct 539 ms 589220 KB Output is correct
3 Correct 535 ms 588652 KB Output is correct
4 Correct 543 ms 588440 KB Output is correct
5 Correct 568 ms 589448 KB Output is correct
6 Correct 539 ms 589492 KB Output is correct
7 Correct 549 ms 589280 KB Output is correct
8 Correct 549 ms 589268 KB Output is correct
9 Correct 578 ms 589224 KB Output is correct
10 Correct 595 ms 588664 KB Output is correct
11 Correct 611 ms 588960 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 588592 KB Output is correct
2 Correct 2951 ms 744312 KB Output is correct
3 Execution timed out 5158 ms 893772 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 588384 KB Output is correct
2 Correct 540 ms 588816 KB Output is correct
3 Correct 545 ms 589020 KB Output is correct
4 Correct 541 ms 588792 KB Output is correct
5 Correct 545 ms 588924 KB Output is correct
6 Correct 536 ms 588828 KB Output is correct
7 Correct 555 ms 588716 KB Output is correct
8 Correct 539 ms 588536 KB Output is correct
9 Correct 537 ms 588792 KB Output is correct
10 Correct 539 ms 588832 KB Output is correct
11 Correct 538 ms 588804 KB Output is correct
12 Correct 543 ms 588892 KB Output is correct
13 Correct 553 ms 588444 KB Output is correct
14 Correct 572 ms 588472 KB Output is correct
15 Correct 599 ms 588504 KB Output is correct
16 Correct 541 ms 588524 KB Output is correct
17 Correct 557 ms 590388 KB Output is correct
18 Correct 549 ms 590440 KB Output is correct
19 Correct 551 ms 590532 KB Output is correct
20 Correct 544 ms 589816 KB Output is correct
21 Correct 547 ms 590120 KB Output is correct
22 Correct 578 ms 590304 KB Output is correct
23 Correct 545 ms 590200 KB Output is correct
24 Correct 542 ms 589844 KB Output is correct
25 Correct 601 ms 597816 KB Output is correct
26 Correct 586 ms 597668 KB Output is correct
27 Correct 636 ms 597768 KB Output is correct
28 Correct 561 ms 593656 KB Output is correct
29 Correct 580 ms 596344 KB Output is correct
30 Correct 584 ms 596588 KB Output is correct
31 Correct 581 ms 596264 KB Output is correct
32 Correct 572 ms 596156 KB Output is correct
33 Correct 877 ms 659456 KB Output is correct
34 Correct 903 ms 659428 KB Output is correct
35 Correct 896 ms 659392 KB Output is correct
36 Correct 979 ms 659432 KB Output is correct
37 Correct 1236 ms 682448 KB Output is correct
38 Correct 1252 ms 682488 KB Output is correct
39 Correct 1252 ms 682732 KB Output is correct
40 Correct 1222 ms 676752 KB Output is correct
41 Correct 791 ms 623736 KB Output is correct
42 Correct 944 ms 631528 KB Output is correct
43 Correct 1468 ms 665332 KB Output is correct
44 Correct 1471 ms 667900 KB Output is correct
45 Correct 927 ms 632440 KB Output is correct
46 Correct 914 ms 628068 KB Output is correct
47 Incorrect 1509 ms 663336 KB Output isn't correct
48 Halted 0 ms 0 KB -