oj.uz

Submission #924701

# Submission time Handle Problem Language Result Execution time Memory
924701 2024-02-09T13:51:29 Z byunjaewoo Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 547736 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int Nmax=2510;
int N, M, A[Nmax][Nmax], L[Nmax][Nmax], R[Nmax][Nmax], D[Nmax][Nmax], U[Nmax][Nmax];
vector<tuple<int, int, int, int>> X, Y;

ll count_rectangles(vector<vector<int> > a) {
	N=a.size(), M=a[0].size();
	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<pair<int, int>> S;
		for(int j=1; j<=M; j++) {
			while(!S.empty() && S.top().first<=A[i][j]) S.pop();
			if(!S.empty()) L[i][j]=S.top().second;
			S.push({A[i][j], j});
		}
		while(!S.empty()) S.pop();
		for(int j=M; j>=1; j--) {
			while(!S.empty() && S.top().first<=A[i][j]) S.pop();
			if(!S.empty()) R[i][j]=S.top().second;
			S.push({A[i][j], j});
		}
	}
	for(int j=1; j<=M; j++) {
		stack<pair<int, int>> S;
		for(int i=1; i<=N; i++) {
			while(!S.empty() && S.top().first<=A[i][j]) S.pop();
			if(!S.empty()) U[i][j]=S.top().second;
			S.push({A[i][j], i});
		}
		while(!S.empty()) S.pop();
		for(int i=N; i>=1; i--) {
			while(!S.empty() && S.top().first<=A[i][j]) S.pop();
			if(!S.empty()) D[i][j]=S.top().second;
			S.push({A[i][j], i});
		}
	}
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
		if(L[i][j] && R[i][j]) X.push_back({L[i][j]+1, R[i][j]-1, i, i});
		if(U[i][j] && D[i][j]) Y.push_back({U[i][j]+1, D[i][j]-1, j, j});
	}
	sort(X.begin(), X.end()), sort(Y.begin(), Y.end());
	X.erase(unique(X.begin(), X.end()), X.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());
	for(int i=(int)X.size()-2; i>=0; i--) {
		auto [l, r, y, v]=X[i];
		auto [ll, rr, yy, vv]=X[i+1];
		if(l==ll && r==rr && y+1==yy) X[i]={l, r, y, vv};
	}
	for(int i=(int)Y.size()-2; i>=0; i--) {
		auto [l, r, x, v]=Y[i];
		auto [ll, rr, xx, vv]=Y[i+1];
		if(l==ll && r==rr && x+1==xx) Y[i]={l, r, x, vv};
	}
	vector<tuple<int, int, int, int>>  ret;
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
		if(!L[i][j] || !R[i][j] || !U[i][j] || !D[i][j]) continue;
		auto p=lower_bound(X.begin(), X.end(), make_tuple(L[i][j]+1, R[i][j]-1, U[i][j]+1, 0));
		if(p==X.end()) continue;
		auto [l, r, y, v]=(*p);
		if(l!=L[i][j]+1 || r!=R[i][j]-1 || y!=U[i][j]+1 || v<D[i][j]-1) continue;
		auto q=lower_bound(Y.begin(), Y.end(), make_tuple(U[i][j]+1, D[i][j]-1, L[i][j]+1, 0));
		if(q==Y.end()) continue;
		auto [ll, rr, xx, vv]=(*q);
		if(ll!=U[i][j]+1 || rr!=D[i][j]-1 || xx!=L[i][j]+1 || vv<R[i][j]-1) continue;
		ret.push_back({L[i][j], R[i][j], U[i][j], D[i][j]});
	}
	sort(ret.begin(), ret.end());
	ret.erase(unique(ret.begin(), ret.end()), ret.end());
	return ret.size();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 18912 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 3 ms 18880 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 2 ms 19036 KB Output is correct
12 Correct 3 ms 19036 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 18912 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 3 ms 18880 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 2 ms 19036 KB Output is correct
12 Correct 3 ms 19036 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 5 ms 19292 KB Output is correct
23 Correct 5 ms 19460 KB Output is correct
24 Correct 5 ms 19548 KB Output is correct
25 Correct 5 ms 19292 KB Output is correct
26 Correct 5 ms 19400 KB Output is correct
27 Correct 5 ms 19292 KB Output is correct
28 Correct 14 ms 19376 KB Output is correct
29 Correct 4 ms 19036 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 18912 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 3 ms 18880 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 2 ms 19036 KB Output is correct
12 Correct 3 ms 19036 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 5 ms 19460 KB Output is correct
19 Correct 5 ms 19548 KB Output is correct
20 Correct 5 ms 19292 KB Output is correct
21 Correct 5 ms 19400 KB Output is correct
22 Correct 5 ms 19292 KB Output is correct
23 Correct 14 ms 19376 KB Output is correct
24 Correct 4 ms 19036 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 3 ms 18780 KB Output is correct
28 Correct 2 ms 12636 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 20 ms 22212 KB Output is correct
31 Correct 20 ms 22216 KB Output is correct
32 Correct 20 ms 22204 KB Output is correct
33 Correct 14 ms 20432 KB Output is correct
34 Correct 21 ms 21024 KB Output is correct
35 Correct 21 ms 21280 KB Output is correct
36 Correct 21 ms 21532 KB Output is correct
37 Correct 21 ms 21280 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 18912 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 3 ms 18880 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 2 ms 19036 KB Output is correct
12 Correct 3 ms 19036 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 5 ms 19460 KB Output is correct
19 Correct 5 ms 19548 KB Output is correct
20 Correct 5 ms 19292 KB Output is correct
21 Correct 5 ms 19400 KB Output is correct
22 Correct 5 ms 19292 KB Output is correct
23 Correct 14 ms 19376 KB Output is correct
24 Correct 4 ms 19036 KB Output is correct
25 Correct 20 ms 22212 KB Output is correct
26 Correct 20 ms 22216 KB Output is correct
27 Correct 20 ms 22204 KB Output is correct
28 Correct 14 ms 20432 KB Output is correct
29 Correct 21 ms 21024 KB Output is correct
30 Correct 21 ms 21280 KB Output is correct
31 Correct 21 ms 21532 KB Output is correct
32 Correct 21 ms 21280 KB Output is correct
33 Correct 1 ms 2396 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct
35 Correct 3 ms 18780 KB Output is correct
36 Correct 2 ms 12636 KB Output is correct
37 Correct 1 ms 4444 KB Output is correct
38 Correct 73 ms 67832 KB Output is correct
39 Correct 69 ms 66436 KB Output is correct
40 Correct 85 ms 68512 KB Output is correct
41 Correct 74 ms 67008 KB Output is correct
42 Correct 255 ms 86148 KB Output is correct
43 Correct 258 ms 86240 KB Output is correct
44 Correct 253 ms 85040 KB Output is correct
45 Correct 240 ms 85232 KB Output is correct
46 Correct 125 ms 63272 KB Output is correct
47 Correct 164 ms 69288 KB Output is correct
48 Correct 262 ms 78884 KB Output is correct
49 Correct 267 ms 79312 KB Output is correct
50 Correct 133 ms 64420 KB Output is correct
51 Correct 129 ms 44516 KB Output is correct
52 Correct 271 ms 79288 KB Output is correct
53 Correct 275 ms 81356 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11100 KB Output is correct
2 Correct 3 ms 11024 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Correct 3 ms 11100 KB Output is correct
8 Correct 3 ms 10952 KB Output is correct
9 Correct 3 ms 11352 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 8792 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 761 ms 152368 KB Output is correct
8 Correct 1761 ms 294912 KB Output is correct
9 Correct 1768 ms 295880 KB Output is correct
10 Correct 1773 ms 295844 KB Output is correct
11 Correct 163 ms 61264 KB Output is correct
12 Correct 312 ms 111188 KB Output is correct
13 Correct 327 ms 114952 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 18912 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 3 ms 18880 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 2 ms 19036 KB Output is correct
12 Correct 3 ms 19036 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 5 ms 19460 KB Output is correct
19 Correct 5 ms 19548 KB Output is correct
20 Correct 5 ms 19292 KB Output is correct
21 Correct 5 ms 19400 KB Output is correct
22 Correct 5 ms 19292 KB Output is correct
23 Correct 14 ms 19376 KB Output is correct
24 Correct 4 ms 19036 KB Output is correct
25 Correct 20 ms 22212 KB Output is correct
26 Correct 20 ms 22216 KB Output is correct
27 Correct 20 ms 22204 KB Output is correct
28 Correct 14 ms 20432 KB Output is correct
29 Correct 21 ms 21024 KB Output is correct
30 Correct 21 ms 21280 KB Output is correct
31 Correct 21 ms 21532 KB Output is correct
32 Correct 21 ms 21280 KB Output is correct
33 Correct 73 ms 67832 KB Output is correct
34 Correct 69 ms 66436 KB Output is correct
35 Correct 85 ms 68512 KB Output is correct
36 Correct 74 ms 67008 KB Output is correct
37 Correct 255 ms 86148 KB Output is correct
38 Correct 258 ms 86240 KB Output is correct
39 Correct 253 ms 85040 KB Output is correct
40 Correct 240 ms 85232 KB Output is correct
41 Correct 125 ms 63272 KB Output is correct
42 Correct 164 ms 69288 KB Output is correct
43 Correct 262 ms 78884 KB Output is correct
44 Correct 267 ms 79312 KB Output is correct
45 Correct 133 ms 64420 KB Output is correct
46 Correct 129 ms 44516 KB Output is correct
47 Correct 271 ms 79288 KB Output is correct
48 Correct 275 ms 81356 KB Output is correct
49 Correct 3 ms 11100 KB Output is correct
50 Correct 3 ms 11024 KB Output is correct
51 Correct 1 ms 4444 KB Output is correct
52 Correct 1 ms 4444 KB Output is correct
53 Correct 3 ms 11096 KB Output is correct
54 Correct 3 ms 11096 KB Output is correct
55 Correct 3 ms 11100 KB Output is correct
56 Correct 3 ms 10952 KB Output is correct
57 Correct 3 ms 11352 KB Output is correct
58 Correct 2 ms 6748 KB Output is correct
59 Correct 2 ms 8792 KB Output is correct
60 Correct 2 ms 12632 KB Output is correct
61 Correct 761 ms 152368 KB Output is correct
62 Correct 1761 ms 294912 KB Output is correct
63 Correct 1768 ms 295880 KB Output is correct
64 Correct 1773 ms 295844 KB Output is correct
65 Correct 163 ms 61264 KB Output is correct
66 Correct 312 ms 111188 KB Output is correct
67 Correct 327 ms 114952 KB Output is correct
68 Correct 1 ms 2396 KB Output is correct
69 Correct 1 ms 6492 KB Output is correct
70 Correct 3 ms 18780 KB Output is correct
71 Correct 2 ms 12636 KB Output is correct
72 Correct 1 ms 4444 KB Output is correct
73 Correct 907 ms 333648 KB Output is correct
74 Correct 916 ms 333580 KB Output is correct
75 Correct 1109 ms 335384 KB Output is correct
76 Correct 937 ms 335008 KB Output is correct
77 Correct 4003 ms 547736 KB Output is correct
78 Correct 2690 ms 299452 KB Output is correct
79 Correct 2924 ms 348264 KB Output is correct
80 Correct 4973 ms 455612 KB Output is correct
81 Correct 2764 ms 314772 KB Output is correct
82 Correct 3944 ms 409144 KB Output is correct
83 Execution timed out 5064 ms 481084 KB Time limit exceeded
84 Halted 0 ms 0 KB -