# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
418249 |
2021-06-05T08:44:38 Z |
Peti |
Rectangles (IOI19_rect) |
C++14 |
|
3640 ms |
1048580 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2505, INF = (int)1e9;
int n, m;
int Y1[maxn][maxn], Y2[maxn][maxn], X1[maxn][maxn], X2[maxn][maxn];
vector<bool> jo;
struct adat{
int l, r, x, ind;
adat(){}
adat(int l, int r, int x, int ind) : l(l), r(r), x(x), ind(ind) {}
};
void calc_elott(vector<vector<int>> &a, function<bool(int, int)> comp){
for(int i = 0; i < n; i++){
Y1[i][0] = -1;
for(int j = 1; j < m; j++){
Y1[i][j] = j-1;
while(Y1[i][j] >= 0 && comp(a[i][Y1[i][j]], a[i][j]))
Y1[i][j] = Y1[i][Y1[i][j]];
}
Y2[i][m-1] = m;
for(int j = m-2; j >= 0; j--){
Y2[i][j] = j+1;
while(Y2[i][j] < m && comp(a[i][Y2[i][j]], a[i][j]))
Y2[i][j] = Y2[i][Y2[i][j]];
}
}
for(int i = 0; i < m; i++){
X1[0][i] = -1;
for(int j = 1; j < n; j++){
X1[j][i] = j-1;
while(X1[j][i] >= 0 && comp(a[X1[j][i]][i], a[j][i]))
X1[j][i] = X1[X1[j][i]][i];
}
X2[n-1][i] = n;
for(int j = n-2; j >= 0; j--){
X2[j][i] = j+1;
while(X2[j][i] < n && comp(a[X2[j][i]][i], a[j][i]))
X2[j][i] = X2[X2[j][i]][i];
}
}
}
vector<adat> U[maxn+1], D[maxn+1], L[maxn+1], R[maxn+1];
pair<int, int> sor[maxn+2];
void ell(int t[], vector<adat> &ints, int n, function<bool(int, int)> comp){
vector<vector<adat>> vh(n);
for(adat &d : ints)
vh[d.r].push_back(d);
int x = 0;
for(int i = 0; i < n; i++){
while(x > 0 && comp(t[i], sor[x-1].second))
x--;
sor[x++] = make_pair(i, t[i]);
for(adat &d : vh[i])
if(comp(lower_bound(sor, sor+x, make_pair(d.l, -INF))->second, d.x))
jo[d.ind] = false;
}
}
vector<pair<int, int>> sarok[maxn][maxn];
bool volt[maxn][maxn] = {};
long long count_rectangles(std::vector<std::vector<int>> a){
n = (int)a.size();
m = (int)a[0].size();
calc_elott(a, [](int a, int b){ return a <= b; });
int ind = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int x1 = X1[i][j], x2 = X2[i][j], y1 = Y1[i][j], y2 = Y2[i][j];
if(x1 != -1 && y1 != -1 && x2 != n && y2 != m)
sarok[x1][y1].emplace_back(x2, y2);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(pair<int, int> &p : sarok[i][j]){
int x1 = i, y1 = j, x2 = p.first, y2 = p.second;
if(volt[x2][y2]) continue;
volt[x2][y2] = true;
U[x1].emplace_back(y1+1, y2-1, x2, ind);
D[x2].emplace_back(y1+1, y2-1, x1, ind);
L[y1].emplace_back(x1+1, x2-1, y2, ind);
R[y2].emplace_back(x1+1, x2-1, y1, ind);
jo.push_back(true);
ind++;
}
for(pair<int, int> &p : sarok[i][j])
volt[p.first][p.second] = false;
}
}
calc_elott(a, [](int a, int b){ return a < b; });
for(int i = 0; i < maxn; i++){
for(int j = i+1; j < maxn; j++){
swap(Y1[i][j], Y1[j][i]);
swap(Y2[i][j], Y2[j][i]);
}
}
for(int i = 0; i < n; i++){
ell(X1[i], D[i], m, [](int a, int b){return a > b;});
ell(X2[i], U[i], m, [](int a, int b){return a < b;});
}
for(int i = 0; i < m; i++){
ell(Y1[i], R[i], n, [](int a, int b){return a > b;});
ell(Y2[i], L[i], n, [](int a, int b){return a < b;});
}
return accumulate(jo.begin(), jo.end(), 0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
196980 KB |
Output is correct |
2 |
Correct |
167 ms |
197360 KB |
Output is correct |
3 |
Correct |
164 ms |
197316 KB |
Output is correct |
4 |
Correct |
162 ms |
197380 KB |
Output is correct |
5 |
Correct |
167 ms |
197220 KB |
Output is correct |
6 |
Correct |
171 ms |
197376 KB |
Output is correct |
7 |
Correct |
167 ms |
197348 KB |
Output is correct |
8 |
Correct |
166 ms |
197092 KB |
Output is correct |
9 |
Correct |
166 ms |
197392 KB |
Output is correct |
10 |
Correct |
163 ms |
197316 KB |
Output is correct |
11 |
Correct |
168 ms |
197292 KB |
Output is correct |
12 |
Correct |
167 ms |
197420 KB |
Output is correct |
13 |
Correct |
167 ms |
196948 KB |
Output is correct |
14 |
Correct |
168 ms |
197072 KB |
Output is correct |
15 |
Correct |
163 ms |
196988 KB |
Output is correct |
16 |
Correct |
164 ms |
196988 KB |
Output is correct |
17 |
Correct |
165 ms |
196932 KB |
Output is correct |
18 |
Correct |
164 ms |
196996 KB |
Output is correct |
19 |
Correct |
164 ms |
197320 KB |
Output is correct |
20 |
Correct |
166 ms |
197256 KB |
Output is correct |
21 |
Correct |
165 ms |
197040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
196980 KB |
Output is correct |
2 |
Correct |
167 ms |
197360 KB |
Output is correct |
3 |
Correct |
164 ms |
197316 KB |
Output is correct |
4 |
Correct |
162 ms |
197380 KB |
Output is correct |
5 |
Correct |
167 ms |
197220 KB |
Output is correct |
6 |
Correct |
171 ms |
197376 KB |
Output is correct |
7 |
Correct |
167 ms |
197348 KB |
Output is correct |
8 |
Correct |
166 ms |
197092 KB |
Output is correct |
9 |
Correct |
166 ms |
197392 KB |
Output is correct |
10 |
Correct |
163 ms |
197316 KB |
Output is correct |
11 |
Correct |
168 ms |
197292 KB |
Output is correct |
12 |
Correct |
167 ms |
197420 KB |
Output is correct |
13 |
Correct |
167 ms |
196948 KB |
Output is correct |
14 |
Correct |
168 ms |
197072 KB |
Output is correct |
15 |
Correct |
163 ms |
196988 KB |
Output is correct |
16 |
Correct |
164 ms |
196988 KB |
Output is correct |
17 |
Correct |
165 ms |
196932 KB |
Output is correct |
18 |
Correct |
164 ms |
196996 KB |
Output is correct |
19 |
Correct |
164 ms |
197320 KB |
Output is correct |
20 |
Correct |
166 ms |
197256 KB |
Output is correct |
21 |
Correct |
165 ms |
197040 KB |
Output is correct |
22 |
Correct |
169 ms |
198712 KB |
Output is correct |
23 |
Correct |
167 ms |
198756 KB |
Output is correct |
24 |
Correct |
169 ms |
198756 KB |
Output is correct |
25 |
Correct |
168 ms |
198304 KB |
Output is correct |
26 |
Correct |
173 ms |
198576 KB |
Output is correct |
27 |
Correct |
173 ms |
198560 KB |
Output is correct |
28 |
Correct |
169 ms |
198508 KB |
Output is correct |
29 |
Correct |
171 ms |
198084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
196980 KB |
Output is correct |
2 |
Correct |
167 ms |
197360 KB |
Output is correct |
3 |
Correct |
164 ms |
197316 KB |
Output is correct |
4 |
Correct |
162 ms |
197380 KB |
Output is correct |
5 |
Correct |
167 ms |
197220 KB |
Output is correct |
6 |
Correct |
171 ms |
197376 KB |
Output is correct |
7 |
Correct |
167 ms |
197348 KB |
Output is correct |
8 |
Correct |
166 ms |
197092 KB |
Output is correct |
9 |
Correct |
166 ms |
197392 KB |
Output is correct |
10 |
Correct |
163 ms |
197316 KB |
Output is correct |
11 |
Correct |
168 ms |
197292 KB |
Output is correct |
12 |
Correct |
167 ms |
197420 KB |
Output is correct |
13 |
Correct |
167 ms |
196948 KB |
Output is correct |
14 |
Correct |
168 ms |
197072 KB |
Output is correct |
15 |
Correct |
163 ms |
196988 KB |
Output is correct |
16 |
Correct |
164 ms |
196988 KB |
Output is correct |
17 |
Correct |
169 ms |
198712 KB |
Output is correct |
18 |
Correct |
167 ms |
198756 KB |
Output is correct |
19 |
Correct |
169 ms |
198756 KB |
Output is correct |
20 |
Correct |
168 ms |
198304 KB |
Output is correct |
21 |
Correct |
173 ms |
198576 KB |
Output is correct |
22 |
Correct |
173 ms |
198560 KB |
Output is correct |
23 |
Correct |
169 ms |
198508 KB |
Output is correct |
24 |
Correct |
171 ms |
198084 KB |
Output is correct |
25 |
Correct |
165 ms |
196932 KB |
Output is correct |
26 |
Correct |
164 ms |
196996 KB |
Output is correct |
27 |
Correct |
164 ms |
197320 KB |
Output is correct |
28 |
Correct |
166 ms |
197256 KB |
Output is correct |
29 |
Correct |
165 ms |
197040 KB |
Output is correct |
30 |
Correct |
187 ms |
205256 KB |
Output is correct |
31 |
Correct |
185 ms |
205176 KB |
Output is correct |
32 |
Correct |
190 ms |
205300 KB |
Output is correct |
33 |
Correct |
189 ms |
202308 KB |
Output is correct |
34 |
Correct |
207 ms |
204108 KB |
Output is correct |
35 |
Correct |
204 ms |
204228 KB |
Output is correct |
36 |
Correct |
200 ms |
203944 KB |
Output is correct |
37 |
Correct |
196 ms |
203912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
196980 KB |
Output is correct |
2 |
Correct |
167 ms |
197360 KB |
Output is correct |
3 |
Correct |
164 ms |
197316 KB |
Output is correct |
4 |
Correct |
162 ms |
197380 KB |
Output is correct |
5 |
Correct |
167 ms |
197220 KB |
Output is correct |
6 |
Correct |
171 ms |
197376 KB |
Output is correct |
7 |
Correct |
167 ms |
197348 KB |
Output is correct |
8 |
Correct |
166 ms |
197092 KB |
Output is correct |
9 |
Correct |
166 ms |
197392 KB |
Output is correct |
10 |
Correct |
163 ms |
197316 KB |
Output is correct |
11 |
Correct |
168 ms |
197292 KB |
Output is correct |
12 |
Correct |
167 ms |
197420 KB |
Output is correct |
13 |
Correct |
167 ms |
196948 KB |
Output is correct |
14 |
Correct |
168 ms |
197072 KB |
Output is correct |
15 |
Correct |
163 ms |
196988 KB |
Output is correct |
16 |
Correct |
164 ms |
196988 KB |
Output is correct |
17 |
Correct |
169 ms |
198712 KB |
Output is correct |
18 |
Correct |
167 ms |
198756 KB |
Output is correct |
19 |
Correct |
169 ms |
198756 KB |
Output is correct |
20 |
Correct |
168 ms |
198304 KB |
Output is correct |
21 |
Correct |
173 ms |
198576 KB |
Output is correct |
22 |
Correct |
173 ms |
198560 KB |
Output is correct |
23 |
Correct |
169 ms |
198508 KB |
Output is correct |
24 |
Correct |
171 ms |
198084 KB |
Output is correct |
25 |
Correct |
187 ms |
205256 KB |
Output is correct |
26 |
Correct |
185 ms |
205176 KB |
Output is correct |
27 |
Correct |
190 ms |
205300 KB |
Output is correct |
28 |
Correct |
189 ms |
202308 KB |
Output is correct |
29 |
Correct |
207 ms |
204108 KB |
Output is correct |
30 |
Correct |
204 ms |
204228 KB |
Output is correct |
31 |
Correct |
200 ms |
203944 KB |
Output is correct |
32 |
Correct |
196 ms |
203912 KB |
Output is correct |
33 |
Correct |
165 ms |
196932 KB |
Output is correct |
34 |
Correct |
164 ms |
196996 KB |
Output is correct |
35 |
Correct |
164 ms |
197320 KB |
Output is correct |
36 |
Correct |
166 ms |
197256 KB |
Output is correct |
37 |
Correct |
165 ms |
197040 KB |
Output is correct |
38 |
Correct |
258 ms |
215324 KB |
Output is correct |
39 |
Correct |
266 ms |
215276 KB |
Output is correct |
40 |
Correct |
263 ms |
215284 KB |
Output is correct |
41 |
Correct |
260 ms |
215296 KB |
Output is correct |
42 |
Correct |
462 ms |
281616 KB |
Output is correct |
43 |
Correct |
431 ms |
281552 KB |
Output is correct |
44 |
Correct |
432 ms |
281892 KB |
Output is correct |
45 |
Correct |
420 ms |
277332 KB |
Output is correct |
46 |
Correct |
422 ms |
240836 KB |
Output is correct |
47 |
Correct |
485 ms |
243648 KB |
Output is correct |
48 |
Correct |
643 ms |
268484 KB |
Output is correct |
49 |
Correct |
666 ms |
270404 KB |
Output is correct |
50 |
Correct |
416 ms |
237048 KB |
Output is correct |
51 |
Correct |
419 ms |
233976 KB |
Output is correct |
52 |
Correct |
581 ms |
260036 KB |
Output is correct |
53 |
Correct |
610 ms |
261904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
197576 KB |
Output is correct |
2 |
Correct |
180 ms |
197488 KB |
Output is correct |
3 |
Correct |
176 ms |
197184 KB |
Output is correct |
4 |
Correct |
170 ms |
196988 KB |
Output is correct |
5 |
Correct |
168 ms |
197388 KB |
Output is correct |
6 |
Correct |
174 ms |
197384 KB |
Output is correct |
7 |
Correct |
172 ms |
197360 KB |
Output is correct |
8 |
Correct |
172 ms |
197288 KB |
Output is correct |
9 |
Correct |
171 ms |
197316 KB |
Output is correct |
10 |
Correct |
175 ms |
197064 KB |
Output is correct |
11 |
Correct |
172 ms |
197196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
196932 KB |
Output is correct |
2 |
Correct |
164 ms |
196996 KB |
Output is correct |
3 |
Correct |
164 ms |
197320 KB |
Output is correct |
4 |
Correct |
166 ms |
197256 KB |
Output is correct |
5 |
Correct |
165 ms |
197040 KB |
Output is correct |
6 |
Correct |
169 ms |
197084 KB |
Output is correct |
7 |
Correct |
1726 ms |
375128 KB |
Output is correct |
8 |
Correct |
3611 ms |
575176 KB |
Output is correct |
9 |
Correct |
3627 ms |
586116 KB |
Output is correct |
10 |
Correct |
3640 ms |
578588 KB |
Output is correct |
11 |
Correct |
745 ms |
251564 KB |
Output is correct |
12 |
Correct |
1311 ms |
303612 KB |
Output is correct |
13 |
Correct |
1377 ms |
307532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
196980 KB |
Output is correct |
2 |
Correct |
167 ms |
197360 KB |
Output is correct |
3 |
Correct |
164 ms |
197316 KB |
Output is correct |
4 |
Correct |
162 ms |
197380 KB |
Output is correct |
5 |
Correct |
167 ms |
197220 KB |
Output is correct |
6 |
Correct |
171 ms |
197376 KB |
Output is correct |
7 |
Correct |
167 ms |
197348 KB |
Output is correct |
8 |
Correct |
166 ms |
197092 KB |
Output is correct |
9 |
Correct |
166 ms |
197392 KB |
Output is correct |
10 |
Correct |
163 ms |
197316 KB |
Output is correct |
11 |
Correct |
168 ms |
197292 KB |
Output is correct |
12 |
Correct |
167 ms |
197420 KB |
Output is correct |
13 |
Correct |
167 ms |
196948 KB |
Output is correct |
14 |
Correct |
168 ms |
197072 KB |
Output is correct |
15 |
Correct |
163 ms |
196988 KB |
Output is correct |
16 |
Correct |
164 ms |
196988 KB |
Output is correct |
17 |
Correct |
169 ms |
198712 KB |
Output is correct |
18 |
Correct |
167 ms |
198756 KB |
Output is correct |
19 |
Correct |
169 ms |
198756 KB |
Output is correct |
20 |
Correct |
168 ms |
198304 KB |
Output is correct |
21 |
Correct |
173 ms |
198576 KB |
Output is correct |
22 |
Correct |
173 ms |
198560 KB |
Output is correct |
23 |
Correct |
169 ms |
198508 KB |
Output is correct |
24 |
Correct |
171 ms |
198084 KB |
Output is correct |
25 |
Correct |
187 ms |
205256 KB |
Output is correct |
26 |
Correct |
185 ms |
205176 KB |
Output is correct |
27 |
Correct |
190 ms |
205300 KB |
Output is correct |
28 |
Correct |
189 ms |
202308 KB |
Output is correct |
29 |
Correct |
207 ms |
204108 KB |
Output is correct |
30 |
Correct |
204 ms |
204228 KB |
Output is correct |
31 |
Correct |
200 ms |
203944 KB |
Output is correct |
32 |
Correct |
196 ms |
203912 KB |
Output is correct |
33 |
Correct |
258 ms |
215324 KB |
Output is correct |
34 |
Correct |
266 ms |
215276 KB |
Output is correct |
35 |
Correct |
263 ms |
215284 KB |
Output is correct |
36 |
Correct |
260 ms |
215296 KB |
Output is correct |
37 |
Correct |
462 ms |
281616 KB |
Output is correct |
38 |
Correct |
431 ms |
281552 KB |
Output is correct |
39 |
Correct |
432 ms |
281892 KB |
Output is correct |
40 |
Correct |
420 ms |
277332 KB |
Output is correct |
41 |
Correct |
422 ms |
240836 KB |
Output is correct |
42 |
Correct |
485 ms |
243648 KB |
Output is correct |
43 |
Correct |
643 ms |
268484 KB |
Output is correct |
44 |
Correct |
666 ms |
270404 KB |
Output is correct |
45 |
Correct |
416 ms |
237048 KB |
Output is correct |
46 |
Correct |
419 ms |
233976 KB |
Output is correct |
47 |
Correct |
581 ms |
260036 KB |
Output is correct |
48 |
Correct |
610 ms |
261904 KB |
Output is correct |
49 |
Correct |
183 ms |
197576 KB |
Output is correct |
50 |
Correct |
180 ms |
197488 KB |
Output is correct |
51 |
Correct |
176 ms |
197184 KB |
Output is correct |
52 |
Correct |
170 ms |
196988 KB |
Output is correct |
53 |
Correct |
168 ms |
197388 KB |
Output is correct |
54 |
Correct |
174 ms |
197384 KB |
Output is correct |
55 |
Correct |
172 ms |
197360 KB |
Output is correct |
56 |
Correct |
172 ms |
197288 KB |
Output is correct |
57 |
Correct |
171 ms |
197316 KB |
Output is correct |
58 |
Correct |
175 ms |
197064 KB |
Output is correct |
59 |
Correct |
172 ms |
197196 KB |
Output is correct |
60 |
Correct |
169 ms |
197084 KB |
Output is correct |
61 |
Correct |
1726 ms |
375128 KB |
Output is correct |
62 |
Correct |
3611 ms |
575176 KB |
Output is correct |
63 |
Correct |
3627 ms |
586116 KB |
Output is correct |
64 |
Correct |
3640 ms |
578588 KB |
Output is correct |
65 |
Correct |
745 ms |
251564 KB |
Output is correct |
66 |
Correct |
1311 ms |
303612 KB |
Output is correct |
67 |
Correct |
1377 ms |
307532 KB |
Output is correct |
68 |
Correct |
165 ms |
196932 KB |
Output is correct |
69 |
Correct |
164 ms |
196996 KB |
Output is correct |
70 |
Correct |
164 ms |
197320 KB |
Output is correct |
71 |
Correct |
166 ms |
197256 KB |
Output is correct |
72 |
Correct |
165 ms |
197040 KB |
Output is correct |
73 |
Correct |
1603 ms |
304156 KB |
Output is correct |
74 |
Correct |
1590 ms |
304000 KB |
Output is correct |
75 |
Correct |
1593 ms |
304048 KB |
Output is correct |
76 |
Correct |
1576 ms |
304024 KB |
Output is correct |
77 |
Runtime error |
3316 ms |
1048580 KB |
Execution killed with signal 9 |
78 |
Halted |
0 ms |
0 KB |
- |