답안 #1060145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1060145	2024-08-15T10:58:34 Z	Unforgettablepl	Rectangles (IOI19_rect)	C++17	59 / 100	5000 ms	28696 KB

rect

#pragma GCC optimize("Ofast","unroll-all-loops")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;


long long count_rectangles(vector<vector<int>> a){
	int n = a.size();
	int m = a[0].size();
	long long ans = 0;
	vector allowedranges(n,vector(n,0));
	for(int i=0;i<m;i++) {
		vector<int> maxi(n);
		for(auto&j:allowedranges)fill(j.begin(), j.end(),0);
		for(int j=i+1;j<m-1;j++) {
			stack<pair<int,int>> s;
			int last_voilater = -1;
			for(int k=0;k<n;k++) {
				maxi[k]=max(maxi[k],a[k][j]);
				if(k!=0 and (maxi[k-1]>=a[k-1][i] or maxi[k-1]>=a[k-1][j+1]))last_voilater=k-1;
				while(!s.empty() and s.top().first<a[k][j])s.pop();
				if(s.empty()) {
					s.emplace(a[k][j],k);
					continue;
				}
				const int l = s.top().second;
				s.emplace(a[k][j],k);
				const int r = k;
				if(r==l+1)continue;
				allowedranges[l][r]++;
				if(l<last_voilater)continue;
				if(allowedranges[l][r]==j-i)ans++;
			}
			s = stack<pair<int,int>>();
			last_voilater = n;
			for(int k=n-1;k>=0;k--) {
				if(k!=n-1 and (maxi[k+1]>=a[k+1][i] or maxi[k+1]>=a[k+1][j+1]))last_voilater=k+1;
				while(!s.empty() and s.top().first<a[k][j])s.pop();
				if(s.empty() or s.top().first==a[k][j]) {
					s.emplace(a[k][j],k);
					continue;
				}
				const int r = s.top().second;
				s.emplace(a[k][j],k);
				const int l = k;
				if(r==l+1)continue;
				allowedranges[l][r]++;
				if(last_voilater<r)continue;
				if(allowedranges[l][r]==j-i)ans++;
			}
		}
	}
	return ans;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	344 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	344 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	4 ms	348 KB	Output is correct
23	Correct	4 ms	512 KB	Output is correct
24	Correct	4 ms	348 KB	Output is correct
25	Correct	6 ms	512 KB	Output is correct
26	Correct	8 ms	512 KB	Output is correct
27	Correct	8 ms	512 KB	Output is correct
28	Correct	7 ms	344 KB	Output is correct
29	Correct	2 ms	400 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	4 ms	348 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	4 ms	348 KB	Output is correct
20	Correct	6 ms	512 KB	Output is correct
21	Correct	8 ms	512 KB	Output is correct
22	Correct	8 ms	512 KB	Output is correct
23	Correct	7 ms	344 KB	Output is correct
24	Correct	2 ms	400 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	344 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	61 ms	900 KB	Output is correct
31	Correct	89 ms	860 KB	Output is correct
32	Correct	68 ms	900 KB	Output is correct
33	Correct	120 ms	864 KB	Output is correct
34	Correct	110 ms	908 KB	Output is correct
35	Correct	113 ms	860 KB	Output is correct
36	Correct	108 ms	900 KB	Output is correct
37	Correct	109 ms	896 KB	Output is correct

Subtask #4
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	4 ms	348 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	4 ms	348 KB	Output is correct
20	Correct	6 ms	512 KB	Output is correct
21	Correct	8 ms	512 KB	Output is correct
22	Correct	8 ms	512 KB	Output is correct
23	Correct	7 ms	344 KB	Output is correct
24	Correct	2 ms	400 KB	Output is correct
25	Correct	61 ms	900 KB	Output is correct
26	Correct	89 ms	860 KB	Output is correct
27	Correct	68 ms	900 KB	Output is correct
28	Correct	120 ms	864 KB	Output is correct
29	Correct	110 ms	908 KB	Output is correct
30	Correct	113 ms	860 KB	Output is correct
31	Correct	108 ms	900 KB	Output is correct
32	Correct	109 ms	896 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	1 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	344 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	2604 ms	6248 KB	Output is correct
39	Correct	2495 ms	6248 KB	Output is correct
40	Correct	2503 ms	6236 KB	Output is correct
41	Correct	2363 ms	6232 KB	Output is correct
42	Correct	2887 ms	6248 KB	Output is correct
43	Correct	3034 ms	6240 KB	Output is correct
44	Correct	2984 ms	6248 KB	Output is correct
45	Correct	2686 ms	5744 KB	Output is correct
46	Correct	3917 ms	6244 KB	Output is correct
47	Correct	4570 ms	6252 KB	Output is correct
48	Correct	4815 ms	6244 KB	Output is correct
49	Correct	4822 ms	9940 KB	Output is correct
50	Correct	1229 ms	6160 KB	Output is correct
51	Correct	2354 ms	4700 KB	Output is correct
52	Correct	4605 ms	9012 KB	Output is correct
53	Correct	4662 ms	9964 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	261 ms	592 KB	Output is correct
2	Correct	220 ms	344 KB	Output is correct
3	Correct	255 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	289 ms	476 KB	Output is correct
6	Correct	288 ms	348 KB	Output is correct
7	Correct	298 ms	480 KB	Output is correct
8	Correct	290 ms	472 KB	Output is correct
9	Correct	296 ms	472 KB	Output is correct
10	Correct	181 ms	344 KB	Output is correct
11	Correct	234 ms	456 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Execution timed out	5092 ms	28696 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	4 ms	348 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	4 ms	348 KB	Output is correct
20	Correct	6 ms	512 KB	Output is correct
21	Correct	8 ms	512 KB	Output is correct
22	Correct	8 ms	512 KB	Output is correct
23	Correct	7 ms	344 KB	Output is correct
24	Correct	2 ms	400 KB	Output is correct
25	Correct	61 ms	900 KB	Output is correct
26	Correct	89 ms	860 KB	Output is correct
27	Correct	68 ms	900 KB	Output is correct
28	Correct	120 ms	864 KB	Output is correct
29	Correct	110 ms	908 KB	Output is correct
30	Correct	113 ms	860 KB	Output is correct
31	Correct	108 ms	900 KB	Output is correct
32	Correct	109 ms	896 KB	Output is correct
33	Correct	2604 ms	6248 KB	Output is correct
34	Correct	2495 ms	6248 KB	Output is correct
35	Correct	2503 ms	6236 KB	Output is correct
36	Correct	2363 ms	6232 KB	Output is correct
37	Correct	2887 ms	6248 KB	Output is correct
38	Correct	3034 ms	6240 KB	Output is correct
39	Correct	2984 ms	6248 KB	Output is correct
40	Correct	2686 ms	5744 KB	Output is correct
41	Correct	3917 ms	6244 KB	Output is correct
42	Correct	4570 ms	6252 KB	Output is correct
43	Correct	4815 ms	6244 KB	Output is correct
44	Correct	4822 ms	9940 KB	Output is correct
45	Correct	1229 ms	6160 KB	Output is correct
46	Correct	2354 ms	4700 KB	Output is correct
47	Correct	4605 ms	9012 KB	Output is correct
48	Correct	4662 ms	9964 KB	Output is correct
49	Correct	261 ms	592 KB	Output is correct
50	Correct	220 ms	344 KB	Output is correct
51	Correct	255 ms	348 KB	Output is correct
52	Correct	0 ms	344 KB	Output is correct
53	Correct	289 ms	476 KB	Output is correct
54	Correct	288 ms	348 KB	Output is correct
55	Correct	298 ms	480 KB	Output is correct
56	Correct	290 ms	472 KB	Output is correct
57	Correct	296 ms	472 KB	Output is correct
58	Correct	181 ms	344 KB	Output is correct
59	Correct	234 ms	456 KB	Output is correct
60	Correct	0 ms	348 KB	Output is correct
61	Execution timed out	5092 ms	28696 KB	Time limit exceeded
62	Halted	0 ms	0 KB	-

답안 #1060145

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 0 / 13.0

Subtask #7 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
0 / 13.0

Subtask #7
0 / 28.0