답안 #143548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143548	2019-08-14T14:33:49 Z	haojiandan	Rectangles (IOI19_rect)	C++14	100 / 100	4195 ms	563760 KB

rect

#include "rect.h"

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=2510;
int n,m,d[maxn][maxn];
int top,st[maxn],N;
int shang[maxn][maxn];
int xia[maxn][maxn];
int zuo[maxn][maxn];
int you[maxn][maxn];
int Y[maxn][maxn]; // you: shang to the min
int Z[maxn][maxn]; // zuo: shang to the min
int X[maxn][maxn]; // xia: zuo to the min
int S[maxn][maxn]; // shang: zuo to the min
set<ll> s;
void add(int x1,int x2,int y1,int y2) {
	if (x2<x1||y2<y1) return;
	if ((you[x2][y1-1]-1==y2&&Y[x2][y1-1]<=x1)||(zuo[x2][y2+1]+1==y1&&Z[x2][y2+1]<=x1))
	if ((xia[x1-1][y2]-1==x2&&X[x1-1][y2]<=y1)||(shang[x2+1][y2]+1==x1&&S[x2+1][y2]<=y1))
		s.insert((ll)(x1-1)*N*N*N+(ll)(x2-1)*N*N+(y1-1)*N+y2-1);
}
ll count_rectangles(vector<vector<int> > a) {
	n=a.size(); m=a[0].size(); N=max(n,m);
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++) d[i+1][j+1]=a[i][j];
	for (int i=1;i<=n;i++) {
		top=0;
		for (int j=1;j<=m;j++) {
			while (top&&d[i][j]>d[i][st[top]]) top--;
			zuo[i][j]=st[top]; st[++top]=j;
		}
		top=0;
		for (int j=m;j>=1;j--) {
			while (top&&d[i][j]>d[i][st[top]]) top--;
			you[i][j]=st[top]; st[++top]=j;
		}
	}
	for (int j=1;j<=m;j++) {
		top=0;
		for (int i=1;i<=n;i++) {
			while (top&&d[i][j]>d[st[top]][j]) top--;
			shang[i][j]=st[top]; st[++top]=i;
		}
		top=0;
		for (int i=n;i>=1;i--) {
			while (top&&d[i][j]>d[st[top]][j]) top--;
			xia[i][j]=st[top]; st[++top]=i;
		}
	}
	for (int j=1;j<=m;j++)
	for (int i=1;i<=n;i++) {
		if (shang[i][j]) {
			if (j>1&&shang[i][j]==shang[i][j-1]) S[i][j]=S[i][j-1];
			else if (j>1&&i==xia[shang[i][j]][j-1]) S[i][j]=X[shang[i][j]][j-1];
			else S[i][j]=j;
		}
		if (xia[i][j]) {
			if (j>1&&xia[i][j]==xia[i][j-1]) X[i][j]=X[i][j-1];
			else if (j>1&&i==shang[xia[i][j]][j-1]) X[i][j]=S[xia[i][j]][j-1];
			else X[i][j]=j;
		}
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++) {
		if (zuo[i][j]) {
			if (i>1&&zuo[i][j]==zuo[i-1][j]) Z[i][j]=Z[i-1][j];
			else if (i>1&&j==you[i-1][zuo[i][j]]) Z[i][j]=Y[i-1][zuo[i][j]];
			else Z[i][j]=i;
		}
		if (you[i][j]) {
			if (i>1&&you[i][j]==you[i-1][j]) Y[i][j]=Y[i-1][j];
			else if (i>1&&j==zuo[i-1][you[i][j]]) Y[i][j]=Z[i-1][you[i][j]];
			else Y[i][j]=i;
		}
	}
	for (int i=2;i<n;i++)
	for (int j=2;j<m;j++) {
		if (shang[i+1][j]&&zuo[i][j+1]) add(shang[i+1][j]+1,i,zuo[i][j+1]+1,j);
		if (shang[i+1][j]&&you[i][j-1]) add(shang[i+1][j]+1,i,j,you[i][j-1]-1);
		if (shang[i+1][j]&&you[shang[i+1][j]+1][j-1])
			add(shang[i+1][j]+1,i,j,you[shang[i+1][j]+1][j-1]-1);
		if (shang[i+1][j]&&zuo[shang[i+1][j]+1][j+1])
			add(shang[i+1][j]+1,i,zuo[shang[i+1][j]+1][j+1]+1,j);
			
		if (xia[i-1][j]&&zuo[i][j+1]) add(i,xia[i-1][j]-1,zuo[i][j+1]+1,j);
		if (xia[i-1][j]&&you[i][j-1]) add(i,xia[i-1][j]-1,j,you[i][j-1]-1);
		if (xia[i-1][j]&&you[xia[i-1][j]-1][j-1])
			add(i,xia[i-1][j]-1,j,you[xia[i-1][j]-1][j-1]-1);
		if (xia[i-1][j]&&zuo[xia[i-1][j]-1][j+1])
			add(i,xia[i-1][j]-1,zuo[xia[i-1][j]-1][j+1]+1,j);
	}
	return s.size();
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	3 ms	1528 KB	Output is correct
4	Correct	3 ms	1532 KB	Output is correct
5	Correct	3 ms	1528 KB	Output is correct
6	Correct	3 ms	1528 KB	Output is correct
7	Correct	3 ms	1528 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	3 ms	1528 KB	Output is correct
11	Correct	3 ms	1528 KB	Output is correct
12	Correct	3 ms	1528 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	760 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	3 ms	1528 KB	Output is correct
20	Correct	3 ms	1528 KB	Output is correct
21	Correct	2 ms	764 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	3 ms	1528 KB	Output is correct
4	Correct	3 ms	1532 KB	Output is correct
5	Correct	3 ms	1528 KB	Output is correct
6	Correct	3 ms	1528 KB	Output is correct
7	Correct	3 ms	1528 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	3 ms	1528 KB	Output is correct
11	Correct	3 ms	1528 KB	Output is correct
12	Correct	3 ms	1528 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	760 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	6 ms	3832 KB	Output is correct
18	Correct	6 ms	3832 KB	Output is correct
19	Correct	6 ms	3832 KB	Output is correct
20	Correct	5 ms	3600 KB	Output is correct
21	Correct	7 ms	3576 KB	Output is correct
22	Correct	6 ms	3704 KB	Output is correct
23	Correct	6 ms	3576 KB	Output is correct
24	Correct	5 ms	3448 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	3 ms	1528 KB	Output is correct
28	Correct	3 ms	1528 KB	Output is correct
29	Correct	2 ms	764 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	3 ms	1528 KB	Output is correct
4	Correct	3 ms	1532 KB	Output is correct
5	Correct	3 ms	1528 KB	Output is correct
6	Correct	3 ms	1528 KB	Output is correct
7	Correct	3 ms	1528 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	3 ms	1528 KB	Output is correct
11	Correct	3 ms	1528 KB	Output is correct
12	Correct	3 ms	1528 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	760 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	6 ms	3832 KB	Output is correct
18	Correct	6 ms	3832 KB	Output is correct
19	Correct	6 ms	3832 KB	Output is correct
20	Correct	5 ms	3600 KB	Output is correct
21	Correct	7 ms	3576 KB	Output is correct
22	Correct	6 ms	3704 KB	Output is correct
23	Correct	6 ms	3576 KB	Output is correct
24	Correct	5 ms	3448 KB	Output is correct
25	Correct	21 ms	11128 KB	Output is correct
26	Correct	19 ms	11100 KB	Output is correct
27	Correct	21 ms	11128 KB	Output is correct
28	Correct	16 ms	9464 KB	Output is correct
29	Correct	20 ms	9976 KB	Output is correct
30	Correct	20 ms	9976 KB	Output is correct
31	Correct	23 ms	9948 KB	Output is correct
32	Correct	20 ms	9820 KB	Output is correct
33	Correct	2 ms	376 KB	Output is correct
34	Correct	2 ms	376 KB	Output is correct
35	Correct	3 ms	1528 KB	Output is correct
36	Correct	3 ms	1528 KB	Output is correct
37	Correct	2 ms	764 KB	Output is correct

Subtask #4
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	3 ms	1528 KB	Output is correct
4	Correct	3 ms	1532 KB	Output is correct
5	Correct	3 ms	1528 KB	Output is correct
6	Correct	3 ms	1528 KB	Output is correct
7	Correct	3 ms	1528 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	3 ms	1528 KB	Output is correct
11	Correct	3 ms	1528 KB	Output is correct
12	Correct	3 ms	1528 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	760 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	6 ms	3832 KB	Output is correct
18	Correct	6 ms	3832 KB	Output is correct
19	Correct	6 ms	3832 KB	Output is correct
20	Correct	5 ms	3600 KB	Output is correct
21	Correct	7 ms	3576 KB	Output is correct
22	Correct	6 ms	3704 KB	Output is correct
23	Correct	6 ms	3576 KB	Output is correct
24	Correct	5 ms	3448 KB	Output is correct
25	Correct	21 ms	11128 KB	Output is correct
26	Correct	19 ms	11100 KB	Output is correct
27	Correct	21 ms	11128 KB	Output is correct
28	Correct	16 ms	9464 KB	Output is correct
29	Correct	20 ms	9976 KB	Output is correct
30	Correct	20 ms	9976 KB	Output is correct
31	Correct	23 ms	9948 KB	Output is correct
32	Correct	20 ms	9820 KB	Output is correct
33	Correct	96 ms	44840 KB	Output is correct
34	Correct	97 ms	44876 KB	Output is correct
35	Correct	94 ms	44928 KB	Output is correct
36	Correct	93 ms	44960 KB	Output is correct
37	Correct	266 ms	69640 KB	Output is correct
38	Correct	291 ms	69528 KB	Output is correct
39	Correct	266 ms	69660 KB	Output is correct
40	Correct	247 ms	65088 KB	Output is correct
41	Correct	132 ms	47700 KB	Output is correct
42	Correct	157 ms	49024 KB	Output is correct
43	Correct	206 ms	54532 KB	Output is correct
44	Correct	214 ms	54616 KB	Output is correct
45	Correct	116 ms	40160 KB	Output is correct
46	Correct	98 ms	27416 KB	Output is correct
47	Correct	208 ms	54524 KB	Output is correct
48	Correct	217 ms	54540 KB	Output is correct
49	Correct	2 ms	376 KB	Output is correct
50	Correct	2 ms	376 KB	Output is correct
51	Correct	3 ms	1528 KB	Output is correct
52	Correct	3 ms	1528 KB	Output is correct
53	Correct	2 ms	764 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	760 KB	Output is correct
2	Correct	3 ms	760 KB	Output is correct
3	Correct	2 ms	760 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	4 ms	764 KB	Output is correct
7	Correct	3 ms	760 KB	Output is correct
8	Correct	3 ms	760 KB	Output is correct
9	Correct	3 ms	760 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	636 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	760 KB	Output is correct
2	Correct	757 ms	137392 KB	Output is correct
3	Correct	1686 ms	281032 KB	Output is correct
4	Correct	1713 ms	282360 KB	Output is correct
5	Correct	1698 ms	282600 KB	Output is correct
6	Correct	524 ms	133752 KB	Output is correct
7	Correct	1100 ms	267560 KB	Output is correct
8	Correct	1162 ms	270604 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	3 ms	1528 KB	Output is correct
12	Correct	3 ms	1528 KB	Output is correct
13	Correct	2 ms	764 KB	Output is correct

Subtask #7
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	3 ms	1528 KB	Output is correct
4	Correct	3 ms	1532 KB	Output is correct
5	Correct	3 ms	1528 KB	Output is correct
6	Correct	3 ms	1528 KB	Output is correct
7	Correct	3 ms	1528 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	3 ms	1528 KB	Output is correct
11	Correct	3 ms	1528 KB	Output is correct
12	Correct	3 ms	1528 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	760 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	6 ms	3832 KB	Output is correct
18	Correct	6 ms	3832 KB	Output is correct
19	Correct	6 ms	3832 KB	Output is correct
20	Correct	5 ms	3600 KB	Output is correct
21	Correct	7 ms	3576 KB	Output is correct
22	Correct	6 ms	3704 KB	Output is correct
23	Correct	6 ms	3576 KB	Output is correct
24	Correct	5 ms	3448 KB	Output is correct
25	Correct	21 ms	11128 KB	Output is correct
26	Correct	19 ms	11100 KB	Output is correct
27	Correct	21 ms	11128 KB	Output is correct
28	Correct	16 ms	9464 KB	Output is correct
29	Correct	20 ms	9976 KB	Output is correct
30	Correct	20 ms	9976 KB	Output is correct
31	Correct	23 ms	9948 KB	Output is correct
32	Correct	20 ms	9820 KB	Output is correct
33	Correct	96 ms	44840 KB	Output is correct
34	Correct	97 ms	44876 KB	Output is correct
35	Correct	94 ms	44928 KB	Output is correct
36	Correct	93 ms	44960 KB	Output is correct
37	Correct	266 ms	69640 KB	Output is correct
38	Correct	291 ms	69528 KB	Output is correct
39	Correct	266 ms	69660 KB	Output is correct
40	Correct	247 ms	65088 KB	Output is correct
41	Correct	132 ms	47700 KB	Output is correct
42	Correct	157 ms	49024 KB	Output is correct
43	Correct	206 ms	54532 KB	Output is correct
44	Correct	214 ms	54616 KB	Output is correct
45	Correct	116 ms	40160 KB	Output is correct
46	Correct	98 ms	27416 KB	Output is correct
47	Correct	208 ms	54524 KB	Output is correct
48	Correct	217 ms	54540 KB	Output is correct
49	Correct	3 ms	760 KB	Output is correct
50	Correct	3 ms	760 KB	Output is correct
51	Correct	2 ms	760 KB	Output is correct
52	Correct	2 ms	504 KB	Output is correct
53	Correct	3 ms	760 KB	Output is correct
54	Correct	4 ms	764 KB	Output is correct
55	Correct	3 ms	760 KB	Output is correct
56	Correct	3 ms	760 KB	Output is correct
57	Correct	3 ms	760 KB	Output is correct
58	Correct	2 ms	504 KB	Output is correct
59	Correct	2 ms	636 KB	Output is correct
60	Correct	2 ms	760 KB	Output is correct
61	Correct	757 ms	137392 KB	Output is correct
62	Correct	1686 ms	281032 KB	Output is correct
63	Correct	1713 ms	282360 KB	Output is correct
64	Correct	1698 ms	282600 KB	Output is correct
65	Correct	524 ms	133752 KB	Output is correct
66	Correct	1100 ms	267560 KB	Output is correct
67	Correct	1162 ms	270604 KB	Output is correct
68	Correct	1282 ms	261940 KB	Output is correct
69	Correct	1329 ms	262124 KB	Output is correct
70	Correct	1256 ms	262072 KB	Output is correct
71	Correct	1306 ms	261964 KB	Output is correct
72	Correct	4124 ms	563732 KB	Output is correct
73	Correct	1622 ms	222504 KB	Output is correct
74	Correct	1821 ms	316092 KB	Output is correct
75	Correct	2780 ms	370480 KB	Output is correct
76	Correct	1666 ms	222856 KB	Output is correct
77	Correct	2345 ms	341496 KB	Output is correct
78	Correct	2865 ms	371348 KB	Output is correct
79	Correct	1639 ms	222452 KB	Output is correct
80	Correct	2855 ms	370756 KB	Output is correct
81	Correct	2770 ms	360512 KB	Output is correct
82	Correct	2394 ms	426704 KB	Output is correct
83	Correct	4090 ms	563344 KB	Output is correct
84	Correct	4195 ms	563604 KB	Output is correct
85	Correct	4130 ms	563760 KB	Output is correct
86	Correct	2 ms	376 KB	Output is correct
87	Correct	2 ms	376 KB	Output is correct
88	Correct	3 ms	1528 KB	Output is correct
89	Correct	3 ms	1528 KB	Output is correct
90	Correct	2 ms	764 KB	Output is correct

답안 #143548

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 7.0 / 7.0

Subtask #3 12.0 / 12.0

Subtask #4 22.0 / 22.0

Subtask #5 10.0 / 10.0

Subtask #6 13.0 / 13.0

Subtask #7 28.0 / 28.0

Subtask #1
8.0 / 8.0

Subtask #2
7.0 / 7.0

Subtask #3
12.0 / 12.0

Subtask #4
22.0 / 22.0

Subtask #5
10.0 / 10.0

Subtask #6
13.0 / 13.0

Subtask #7
28.0 / 28.0