# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
796753 | 2023-07-28T17:13:26 Z | lukameladze | Rectangles (IOI19_rect) | C++17 | 2919 ms | 1048576 KB |
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define f first #define s second #define pii pair <short, short> #define pb push_back const int N = 2501; short n, m, sf[N][N], pr[N][N], pr_u[N][N], sf_d[N][N]; int a[N][N]; set <pii> s[N], sj[N]; set <array <short , 3> > dp[N], dpj[N]; short get(short i, short l, short r) { auto it = dp[i].lower_bound({l, r, 0}); short res = 0; if ((*it)[0] == l && (*it)[1] == r) { res = (*it)[2]; } return res; } short getj(short j, short l, short r) { auto it = dpj[j].lower_bound({l, r, 0}); short res = 0; if ((*it)[0] == l && (*it)[1] == r) { res = (*it)[2]; } return res; } long long count_rectangles(vector<vector<int> > x) { n = x.size(); for (int i = 0; i < n; i++) { m = x[i].size(); for (int j = 0; j < m; j++) { a[i][j] = x[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int cur = j - 1; while (cur >= 0 && a[i][cur] <= a[i][j]) { cur = pr[i][cur]; } pr[i][j] = cur; } for (int j = m - 1; j >= 0; j--) { int cur = j + 1; while (cur < m && a[i][cur] <= a[i][j]) { cur = sf[i][cur]; } sf[i][j] = cur; int l = pr[i][j] + 1, r = sf[i][j] - 1; if (l != 0 && r != m - 1) s[i].insert({l, r}); } } for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) { int cur = i - 1; while (cur >= 0 && a[cur][j] <= a[i][j]) { cur = pr_u[cur][j]; } pr_u[i][j] = cur; } for (int i = n - 1; i >= 0; i--) { int cur = i + 1; while (cur < n && a[cur][j] <= a[i][j]) { cur = sf_d[cur][j]; } sf_d[i][j] = cur; int l = pr_u[i][j] + 1, r = sf_d[i][j] - 1; if (l != 0 && r != n - 1) sj[j].insert({l, r}); } } for (int i = 0; i < n; i++) { for (pii sth : s[i]) { int l = sth.f, r = sth.s; if (i == 0) { dp[i].insert({l, r, 1}); continue; } dp[i].insert({l, r, get(i - 1, l, r) + 1}); } } for (int j = 0; j < m; j++) { for (pii sth : sj[j]) { int l = sth.f, r = sth.s; if (j == 0) { dpj[j].insert({l, r, 1}); continue; } dpj[j].insert({l, r, getj(j - 1, l, r) + 1}); } } set <array <short, 4> > ans; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int xu = pr_u[i][j] + 1, yu = pr[i][j] + 1; int xd = sf_d[i][j] - 1, yd = sf[i][j] - 1; if (xu == 0 || yu == 0 || xd == n - 1 || yd == m - 1) continue; if (get(xd, yu, yd) >= (xd - xu + 1) && getj(yd, xu, xd) >= (yd - yu + 1)) ans.insert({xu, yu, xd, yd}); } } return (int)ans.size(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 852 KB | Output is correct |
2 | Correct | 2 ms | 1640 KB | Output is correct |
3 | Correct | 2 ms | 1492 KB | Output is correct |
4 | Correct | 1 ms | 1492 KB | Output is correct |
5 | Correct | 1 ms | 1364 KB | Output is correct |
6 | Correct | 1 ms | 1492 KB | Output is correct |
7 | Correct | 1 ms | 1364 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Correct | 1 ms | 1492 KB | Output is correct |
10 | Correct | 1 ms | 1492 KB | Output is correct |
11 | Correct | 2 ms | 1492 KB | Output is correct |
12 | Correct | 1 ms | 1492 KB | Output is correct |
13 | Correct | 1 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 980 KB | Output is correct |
15 | Correct | 1 ms | 980 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 1 ms | 776 KB | Output is correct |
18 | Correct | 1 ms | 784 KB | Output is correct |
19 | Correct | 1 ms | 1364 KB | Output is correct |
20 | Correct | 1 ms | 1364 KB | Output is correct |
21 | Correct | 1 ms | 980 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 852 KB | Output is correct |
2 | Correct | 2 ms | 1640 KB | Output is correct |
3 | Correct | 2 ms | 1492 KB | Output is correct |
4 | Correct | 1 ms | 1492 KB | Output is correct |
5 | Correct | 1 ms | 1364 KB | Output is correct |
6 | Correct | 1 ms | 1492 KB | Output is correct |
7 | Correct | 1 ms | 1364 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Correct | 1 ms | 1492 KB | Output is correct |
10 | Correct | 1 ms | 1492 KB | Output is correct |
11 | Correct | 2 ms | 1492 KB | Output is correct |
12 | Correct | 1 ms | 1492 KB | Output is correct |
13 | Correct | 1 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 980 KB | Output is correct |
15 | Correct | 1 ms | 980 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 1 ms | 776 KB | Output is correct |
18 | Correct | 1 ms | 784 KB | Output is correct |
19 | Correct | 1 ms | 1364 KB | Output is correct |
20 | Correct | 1 ms | 1364 KB | Output is correct |
21 | Correct | 1 ms | 980 KB | Output is correct |
22 | Correct | 5 ms | 3924 KB | Output is correct |
23 | Correct | 5 ms | 3924 KB | Output is correct |
24 | Correct | 5 ms | 3924 KB | Output is correct |
25 | Correct | 4 ms | 2964 KB | Output is correct |
26 | Correct | 5 ms | 3612 KB | Output is correct |
27 | Correct | 5 ms | 3604 KB | Output is correct |
28 | Correct | 5 ms | 3540 KB | Output is correct |
29 | Correct | 3 ms | 2900 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 852 KB | Output is correct |
2 | Correct | 2 ms | 1640 KB | Output is correct |
3 | Correct | 2 ms | 1492 KB | Output is correct |
4 | Correct | 1 ms | 1492 KB | Output is correct |
5 | Correct | 1 ms | 1364 KB | Output is correct |
6 | Correct | 1 ms | 1492 KB | Output is correct |
7 | Correct | 1 ms | 1364 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Correct | 1 ms | 1492 KB | Output is correct |
10 | Correct | 1 ms | 1492 KB | Output is correct |
11 | Correct | 2 ms | 1492 KB | Output is correct |
12 | Correct | 1 ms | 1492 KB | Output is correct |
13 | Correct | 1 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 980 KB | Output is correct |
15 | Correct | 1 ms | 980 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 5 ms | 3924 KB | Output is correct |
18 | Correct | 5 ms | 3924 KB | Output is correct |
19 | Correct | 5 ms | 3924 KB | Output is correct |
20 | Correct | 4 ms | 2964 KB | Output is correct |
21 | Correct | 5 ms | 3612 KB | Output is correct |
22 | Correct | 5 ms | 3604 KB | Output is correct |
23 | Correct | 5 ms | 3540 KB | Output is correct |
24 | Correct | 3 ms | 2900 KB | Output is correct |
25 | Correct | 1 ms | 776 KB | Output is correct |
26 | Correct | 1 ms | 784 KB | Output is correct |
27 | Correct | 1 ms | 1364 KB | Output is correct |
28 | Correct | 1 ms | 1364 KB | Output is correct |
29 | Correct | 1 ms | 980 KB | Output is correct |
30 | Correct | 35 ms | 14952 KB | Output is correct |
31 | Correct | 30 ms | 14952 KB | Output is correct |
32 | Correct | 31 ms | 15068 KB | Output is correct |
33 | Correct | 15 ms | 8660 KB | Output is correct |
34 | Correct | 32 ms | 13268 KB | Output is correct |
35 | Correct | 39 ms | 13596 KB | Output is correct |
36 | Correct | 32 ms | 12976 KB | Output is correct |
37 | Correct | 31 ms | 12908 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 852 KB | Output is correct |
2 | Correct | 2 ms | 1640 KB | Output is correct |
3 | Correct | 2 ms | 1492 KB | Output is correct |
4 | Correct | 1 ms | 1492 KB | Output is correct |
5 | Correct | 1 ms | 1364 KB | Output is correct |
6 | Correct | 1 ms | 1492 KB | Output is correct |
7 | Correct | 1 ms | 1364 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Correct | 1 ms | 1492 KB | Output is correct |
10 | Correct | 1 ms | 1492 KB | Output is correct |
11 | Correct | 2 ms | 1492 KB | Output is correct |
12 | Correct | 1 ms | 1492 KB | Output is correct |
13 | Correct | 1 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 980 KB | Output is correct |
15 | Correct | 1 ms | 980 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 5 ms | 3924 KB | Output is correct |
18 | Correct | 5 ms | 3924 KB | Output is correct |
19 | Correct | 5 ms | 3924 KB | Output is correct |
20 | Correct | 4 ms | 2964 KB | Output is correct |
21 | Correct | 5 ms | 3612 KB | Output is correct |
22 | Correct | 5 ms | 3604 KB | Output is correct |
23 | Correct | 5 ms | 3540 KB | Output is correct |
24 | Correct | 3 ms | 2900 KB | Output is correct |
25 | Correct | 35 ms | 14952 KB | Output is correct |
26 | Correct | 30 ms | 14952 KB | Output is correct |
27 | Correct | 31 ms | 15068 KB | Output is correct |
28 | Correct | 15 ms | 8660 KB | Output is correct |
29 | Correct | 32 ms | 13268 KB | Output is correct |
30 | Correct | 39 ms | 13596 KB | Output is correct |
31 | Correct | 32 ms | 12976 KB | Output is correct |
32 | Correct | 31 ms | 12908 KB | Output is correct |
33 | Correct | 1 ms | 776 KB | Output is correct |
34 | Correct | 1 ms | 784 KB | Output is correct |
35 | Correct | 1 ms | 1364 KB | Output is correct |
36 | Correct | 1 ms | 1364 KB | Output is correct |
37 | Correct | 1 ms | 980 KB | Output is correct |
38 | Correct | 165 ms | 72060 KB | Output is correct |
39 | Correct | 167 ms | 72056 KB | Output is correct |
40 | Correct | 169 ms | 72084 KB | Output is correct |
41 | Correct | 157 ms | 72076 KB | Output is correct |
42 | Correct | 433 ms | 140804 KB | Output is correct |
43 | Correct | 453 ms | 140748 KB | Output is correct |
44 | Correct | 434 ms | 141144 KB | Output is correct |
45 | Correct | 439 ms | 132108 KB | Output is correct |
46 | Correct | 122 ms | 47804 KB | Output is correct |
47 | Correct | 194 ms | 62044 KB | Output is correct |
48 | Correct | 479 ms | 121800 KB | Output is correct |
49 | Correct | 474 ms | 124924 KB | Output is correct |
50 | Correct | 230 ms | 70084 KB | Output is correct |
51 | Correct | 227 ms | 62480 KB | Output is correct |
52 | Correct | 477 ms | 116396 KB | Output is correct |
53 | Correct | 462 ms | 117612 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2004 KB | Output is correct |
2 | Correct | 3 ms | 1876 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 852 KB | Output is correct |
5 | Correct | 4 ms | 1748 KB | Output is correct |
6 | Correct | 3 ms | 1776 KB | Output is correct |
7 | Correct | 4 ms | 1748 KB | Output is correct |
8 | Correct | 4 ms | 1748 KB | Output is correct |
9 | Correct | 3 ms | 1748 KB | Output is correct |
10 | Correct | 1 ms | 1108 KB | Output is correct |
11 | Correct | 2 ms | 1348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 776 KB | Output is correct |
2 | Correct | 1 ms | 784 KB | Output is correct |
3 | Correct | 1 ms | 1364 KB | Output is correct |
4 | Correct | 1 ms | 1364 KB | Output is correct |
5 | Correct | 1 ms | 980 KB | Output is correct |
6 | Correct | 1 ms | 980 KB | Output is correct |
7 | Correct | 794 ms | 204268 KB | Output is correct |
8 | Correct | 1980 ms | 438100 KB | Output is correct |
9 | Correct | 1912 ms | 440364 KB | Output is correct |
10 | Correct | 1944 ms | 440548 KB | Output is correct |
11 | Correct | 172 ms | 67272 KB | Output is correct |
12 | Correct | 395 ms | 131692 KB | Output is correct |
13 | Correct | 389 ms | 135504 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 852 KB | Output is correct |
2 | Correct | 2 ms | 1640 KB | Output is correct |
3 | Correct | 2 ms | 1492 KB | Output is correct |
4 | Correct | 1 ms | 1492 KB | Output is correct |
5 | Correct | 1 ms | 1364 KB | Output is correct |
6 | Correct | 1 ms | 1492 KB | Output is correct |
7 | Correct | 1 ms | 1364 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Correct | 1 ms | 1492 KB | Output is correct |
10 | Correct | 1 ms | 1492 KB | Output is correct |
11 | Correct | 2 ms | 1492 KB | Output is correct |
12 | Correct | 1 ms | 1492 KB | Output is correct |
13 | Correct | 1 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 980 KB | Output is correct |
15 | Correct | 1 ms | 980 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 5 ms | 3924 KB | Output is correct |
18 | Correct | 5 ms | 3924 KB | Output is correct |
19 | Correct | 5 ms | 3924 KB | Output is correct |
20 | Correct | 4 ms | 2964 KB | Output is correct |
21 | Correct | 5 ms | 3612 KB | Output is correct |
22 | Correct | 5 ms | 3604 KB | Output is correct |
23 | Correct | 5 ms | 3540 KB | Output is correct |
24 | Correct | 3 ms | 2900 KB | Output is correct |
25 | Correct | 35 ms | 14952 KB | Output is correct |
26 | Correct | 30 ms | 14952 KB | Output is correct |
27 | Correct | 31 ms | 15068 KB | Output is correct |
28 | Correct | 15 ms | 8660 KB | Output is correct |
29 | Correct | 32 ms | 13268 KB | Output is correct |
30 | Correct | 39 ms | 13596 KB | Output is correct |
31 | Correct | 32 ms | 12976 KB | Output is correct |
32 | Correct | 31 ms | 12908 KB | Output is correct |
33 | Correct | 165 ms | 72060 KB | Output is correct |
34 | Correct | 167 ms | 72056 KB | Output is correct |
35 | Correct | 169 ms | 72084 KB | Output is correct |
36 | Correct | 157 ms | 72076 KB | Output is correct |
37 | Correct | 433 ms | 140804 KB | Output is correct |
38 | Correct | 453 ms | 140748 KB | Output is correct |
39 | Correct | 434 ms | 141144 KB | Output is correct |
40 | Correct | 439 ms | 132108 KB | Output is correct |
41 | Correct | 122 ms | 47804 KB | Output is correct |
42 | Correct | 194 ms | 62044 KB | Output is correct |
43 | Correct | 479 ms | 121800 KB | Output is correct |
44 | Correct | 474 ms | 124924 KB | Output is correct |
45 | Correct | 230 ms | 70084 KB | Output is correct |
46 | Correct | 227 ms | 62480 KB | Output is correct |
47 | Correct | 477 ms | 116396 KB | Output is correct |
48 | Correct | 462 ms | 117612 KB | Output is correct |
49 | Correct | 4 ms | 2004 KB | Output is correct |
50 | Correct | 3 ms | 1876 KB | Output is correct |
51 | Correct | 1 ms | 980 KB | Output is correct |
52 | Correct | 1 ms | 852 KB | Output is correct |
53 | Correct | 4 ms | 1748 KB | Output is correct |
54 | Correct | 3 ms | 1776 KB | Output is correct |
55 | Correct | 4 ms | 1748 KB | Output is correct |
56 | Correct | 4 ms | 1748 KB | Output is correct |
57 | Correct | 3 ms | 1748 KB | Output is correct |
58 | Correct | 1 ms | 1108 KB | Output is correct |
59 | Correct | 2 ms | 1348 KB | Output is correct |
60 | Correct | 1 ms | 980 KB | Output is correct |
61 | Correct | 794 ms | 204268 KB | Output is correct |
62 | Correct | 1980 ms | 438100 KB | Output is correct |
63 | Correct | 1912 ms | 440364 KB | Output is correct |
64 | Correct | 1944 ms | 440548 KB | Output is correct |
65 | Correct | 172 ms | 67272 KB | Output is correct |
66 | Correct | 395 ms | 131692 KB | Output is correct |
67 | Correct | 389 ms | 135504 KB | Output is correct |
68 | Correct | 1 ms | 776 KB | Output is correct |
69 | Correct | 1 ms | 784 KB | Output is correct |
70 | Correct | 1 ms | 1364 KB | Output is correct |
71 | Correct | 1 ms | 1364 KB | Output is correct |
72 | Correct | 1 ms | 980 KB | Output is correct |
73 | Correct | 2472 ms | 756440 KB | Output is correct |
74 | Correct | 2399 ms | 756536 KB | Output is correct |
75 | Correct | 2382 ms | 756392 KB | Output is correct |
76 | Correct | 2244 ms | 756492 KB | Output is correct |
77 | Runtime error | 2919 ms | 1048576 KB | Execution killed with signal 9 |
78 | Halted | 0 ms | 0 KB | - |