# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
153777 |
2019-09-16T05:42:24 Z |
myungwoo |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
495096 KB |
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define fr first
#define sc second
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long lld;
typedef pair<int, int> pii;
int N, M;
int A[2502][2502];
pii ver[2502][2502], hor[2502][2502];
struct SEGMENT {
int a, b, t, dp;
bool operator < (const SEGMENT &ot)const{
if (t != ot.t) return t < ot.t;
if (a != ot.a) return a < ot.a;
return b < ot.b;
}
};
vector <SEGMENT> container;
bool cmp_segment(const int &a, const int &b){
return container[a] < container[b];
}
lld count_rectangles(vector<vector<int>> a)
{
N = sz(a); M = sz(a[0]);
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 <int> stk;
for (int j=1;j<=M;j++){
while (!stk.empty() && A[i][stk.top()] <= A[i][j]) stk.pop();
hor[i][j].fr = stk.empty() ? 1 : stk.top()+1;
stk.push(j);
}
stk = {};
for (int j=M;j;j--){
while (!stk.empty() && A[i][stk.top()] <= A[i][j]) stk.pop();
hor[i][j].sc = stk.empty() ? M : stk.top()-1;
stk.push(j);
}
}
for (int j=1;j<=M;j++){
stack <int> stk;
for (int i=1;i<=N;i++){
while (!stk.empty() && A[stk.top()][j] <= A[i][j]) stk.pop();
ver[i][j].fr = stk.empty() ? 1 : stk.top()+1;
stk.push(i);
}
stk = {};
for (int i=N;i;i--){
while (!stk.empty() && A[stk.top()][j] <= A[i][j]) stk.pop();
ver[i][j].sc = stk.empty() ? N : stk.top()-1;
stk.push(i);
}
}
vector <int> vertical, horizontal;
for (int j=1;j<=M;j++) for (int i=1;i<=N;i++){
const auto &sg = ver[i][j];
vertical.push_back(sz(container));
container.push_back({sg.fr, sg.sc, j});
}
for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
const auto &sg = hor[i][j];
horizontal.push_back(sz(container));
container.push_back({sg.fr, sg.sc, i});
}
sort(all(vertical), cmp_segment);
sort(all(horizontal), cmp_segment);
const auto do_dp = [](const vector<int> &arr){
for (auto i=arr.begin(),j=i;i!=arr.end();i++){
static auto f = [](int p, int q){
const auto &a = container[p];
auto b = container[q]; b.t--;
return a < b;
};
while (f(*j, *i)) j++;
auto &p = container[*j], &q = container[*i];
if (p.t == q.t-1 && p.a == q.a && p.b == q.b) q.dp = p.dp+1;
else q.dp = 1;
}
};
do_dp(vertical);
do_dp(horizontal);
const auto get = [](const vector<int> &arr, int a, int b, int t){
SEGMENT sg = {a, b, t};
int s = 0, e = sz(arr)-1, ret = sz(arr);
while (s <= e){
int m = s+e >> 1;
auto &v = container[arr[m]];
if (v < sg) s = m+1;
else ret = m, e = m-1;
}
if (ret == sz(arr)) return 0;
auto &v = container[arr[ret]];
if (v.t == t && v.a == a && v.b == b) return v.dp;
return 0;
};
set <lld> vis;
for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
int sy = ver[i][j].fr, ey = ver[i][j].sc;
int sx = hor[i][j].fr, ex = hor[i][j].sc;
if (sy == 1 || ey == N || sx == 1 || ex == M) continue;
if (get(vertical, sy, ey, ex) <= ex-sx || get(horizontal, sx, ex, ey) <= ey-sy) continue;
lld v = (lld)((sy-1)*M+sx-1)*N*M + (ey-1)*M+ex-1;
if (vis.count(v)) continue;
vis.insert(v);
}
return sz(vis);
}
Compilation message
rect.cpp: In lambda function:
rect.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
760 KB |
Output is correct |
3 |
Correct |
3 ms |
760 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
6 |
Correct |
3 ms |
760 KB |
Output is correct |
7 |
Correct |
3 ms |
760 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
760 KB |
Output is correct |
10 |
Correct |
3 ms |
760 KB |
Output is correct |
11 |
Correct |
3 ms |
760 KB |
Output is correct |
12 |
Correct |
3 ms |
760 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
760 KB |
Output is correct |
20 |
Correct |
3 ms |
760 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
760 KB |
Output is correct |
3 |
Correct |
3 ms |
760 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
6 |
Correct |
3 ms |
760 KB |
Output is correct |
7 |
Correct |
3 ms |
760 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
760 KB |
Output is correct |
10 |
Correct |
3 ms |
760 KB |
Output is correct |
11 |
Correct |
3 ms |
760 KB |
Output is correct |
12 |
Correct |
3 ms |
760 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
2036 KB |
Output is correct |
18 |
Correct |
7 ms |
2036 KB |
Output is correct |
19 |
Correct |
7 ms |
2036 KB |
Output is correct |
20 |
Correct |
6 ms |
1912 KB |
Output is correct |
21 |
Correct |
7 ms |
1960 KB |
Output is correct |
22 |
Correct |
7 ms |
1912 KB |
Output is correct |
23 |
Correct |
7 ms |
1912 KB |
Output is correct |
24 |
Correct |
5 ms |
1660 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
760 KB |
Output is correct |
28 |
Correct |
3 ms |
760 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
760 KB |
Output is correct |
3 |
Correct |
3 ms |
760 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
6 |
Correct |
3 ms |
760 KB |
Output is correct |
7 |
Correct |
3 ms |
760 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
760 KB |
Output is correct |
10 |
Correct |
3 ms |
760 KB |
Output is correct |
11 |
Correct |
3 ms |
760 KB |
Output is correct |
12 |
Correct |
3 ms |
760 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
2036 KB |
Output is correct |
18 |
Correct |
7 ms |
2036 KB |
Output is correct |
19 |
Correct |
7 ms |
2036 KB |
Output is correct |
20 |
Correct |
6 ms |
1912 KB |
Output is correct |
21 |
Correct |
7 ms |
1960 KB |
Output is correct |
22 |
Correct |
7 ms |
1912 KB |
Output is correct |
23 |
Correct |
7 ms |
1912 KB |
Output is correct |
24 |
Correct |
5 ms |
1660 KB |
Output is correct |
25 |
Correct |
38 ms |
7656 KB |
Output is correct |
26 |
Correct |
39 ms |
7528 KB |
Output is correct |
27 |
Correct |
39 ms |
7784 KB |
Output is correct |
28 |
Correct |
27 ms |
6508 KB |
Output is correct |
29 |
Correct |
34 ms |
6508 KB |
Output is correct |
30 |
Correct |
35 ms |
6764 KB |
Output is correct |
31 |
Correct |
36 ms |
6764 KB |
Output is correct |
32 |
Correct |
35 ms |
6636 KB |
Output is correct |
33 |
Correct |
3 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
3 ms |
760 KB |
Output is correct |
36 |
Correct |
3 ms |
760 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
760 KB |
Output is correct |
3 |
Correct |
3 ms |
760 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
6 |
Correct |
3 ms |
760 KB |
Output is correct |
7 |
Correct |
3 ms |
760 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
760 KB |
Output is correct |
10 |
Correct |
3 ms |
760 KB |
Output is correct |
11 |
Correct |
3 ms |
760 KB |
Output is correct |
12 |
Correct |
3 ms |
760 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
2036 KB |
Output is correct |
18 |
Correct |
7 ms |
2036 KB |
Output is correct |
19 |
Correct |
7 ms |
2036 KB |
Output is correct |
20 |
Correct |
6 ms |
1912 KB |
Output is correct |
21 |
Correct |
7 ms |
1960 KB |
Output is correct |
22 |
Correct |
7 ms |
1912 KB |
Output is correct |
23 |
Correct |
7 ms |
1912 KB |
Output is correct |
24 |
Correct |
5 ms |
1660 KB |
Output is correct |
25 |
Correct |
38 ms |
7656 KB |
Output is correct |
26 |
Correct |
39 ms |
7528 KB |
Output is correct |
27 |
Correct |
39 ms |
7784 KB |
Output is correct |
28 |
Correct |
27 ms |
6508 KB |
Output is correct |
29 |
Correct |
34 ms |
6508 KB |
Output is correct |
30 |
Correct |
35 ms |
6764 KB |
Output is correct |
31 |
Correct |
36 ms |
6764 KB |
Output is correct |
32 |
Correct |
35 ms |
6636 KB |
Output is correct |
33 |
Correct |
242 ms |
45884 KB |
Output is correct |
34 |
Correct |
221 ms |
46652 KB |
Output is correct |
35 |
Correct |
248 ms |
46656 KB |
Output is correct |
36 |
Correct |
211 ms |
45776 KB |
Output is correct |
37 |
Correct |
601 ms |
67680 KB |
Output is correct |
38 |
Correct |
626 ms |
67544 KB |
Output is correct |
39 |
Correct |
650 ms |
67964 KB |
Output is correct |
40 |
Correct |
573 ms |
63552 KB |
Output is correct |
41 |
Correct |
309 ms |
44588 KB |
Output is correct |
42 |
Correct |
365 ms |
44732 KB |
Output is correct |
43 |
Correct |
509 ms |
51132 KB |
Output is correct |
44 |
Correct |
488 ms |
52924 KB |
Output is correct |
45 |
Correct |
243 ms |
31056 KB |
Output is correct |
46 |
Correct |
225 ms |
26708 KB |
Output is correct |
47 |
Correct |
508 ms |
52032 KB |
Output is correct |
48 |
Correct |
515 ms |
53052 KB |
Output is correct |
49 |
Correct |
3 ms |
376 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
3 ms |
760 KB |
Output is correct |
52 |
Correct |
3 ms |
760 KB |
Output is correct |
53 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1016 KB |
Output is correct |
2 |
Correct |
6 ms |
1016 KB |
Output is correct |
3 |
Correct |
4 ms |
920 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
1016 KB |
Output is correct |
6 |
Correct |
6 ms |
1016 KB |
Output is correct |
7 |
Correct |
6 ms |
1016 KB |
Output is correct |
8 |
Correct |
6 ms |
1016 KB |
Output is correct |
9 |
Correct |
6 ms |
1016 KB |
Output is correct |
10 |
Correct |
4 ms |
636 KB |
Output is correct |
11 |
Correct |
4 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2185 ms |
253200 KB |
Output is correct |
3 |
Execution timed out |
5101 ms |
495096 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
760 KB |
Output is correct |
3 |
Correct |
3 ms |
760 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
6 |
Correct |
3 ms |
760 KB |
Output is correct |
7 |
Correct |
3 ms |
760 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
760 KB |
Output is correct |
10 |
Correct |
3 ms |
760 KB |
Output is correct |
11 |
Correct |
3 ms |
760 KB |
Output is correct |
12 |
Correct |
3 ms |
760 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
2036 KB |
Output is correct |
18 |
Correct |
7 ms |
2036 KB |
Output is correct |
19 |
Correct |
7 ms |
2036 KB |
Output is correct |
20 |
Correct |
6 ms |
1912 KB |
Output is correct |
21 |
Correct |
7 ms |
1960 KB |
Output is correct |
22 |
Correct |
7 ms |
1912 KB |
Output is correct |
23 |
Correct |
7 ms |
1912 KB |
Output is correct |
24 |
Correct |
5 ms |
1660 KB |
Output is correct |
25 |
Correct |
38 ms |
7656 KB |
Output is correct |
26 |
Correct |
39 ms |
7528 KB |
Output is correct |
27 |
Correct |
39 ms |
7784 KB |
Output is correct |
28 |
Correct |
27 ms |
6508 KB |
Output is correct |
29 |
Correct |
34 ms |
6508 KB |
Output is correct |
30 |
Correct |
35 ms |
6764 KB |
Output is correct |
31 |
Correct |
36 ms |
6764 KB |
Output is correct |
32 |
Correct |
35 ms |
6636 KB |
Output is correct |
33 |
Correct |
242 ms |
45884 KB |
Output is correct |
34 |
Correct |
221 ms |
46652 KB |
Output is correct |
35 |
Correct |
248 ms |
46656 KB |
Output is correct |
36 |
Correct |
211 ms |
45776 KB |
Output is correct |
37 |
Correct |
601 ms |
67680 KB |
Output is correct |
38 |
Correct |
626 ms |
67544 KB |
Output is correct |
39 |
Correct |
650 ms |
67964 KB |
Output is correct |
40 |
Correct |
573 ms |
63552 KB |
Output is correct |
41 |
Correct |
309 ms |
44588 KB |
Output is correct |
42 |
Correct |
365 ms |
44732 KB |
Output is correct |
43 |
Correct |
509 ms |
51132 KB |
Output is correct |
44 |
Correct |
488 ms |
52924 KB |
Output is correct |
45 |
Correct |
243 ms |
31056 KB |
Output is correct |
46 |
Correct |
225 ms |
26708 KB |
Output is correct |
47 |
Correct |
508 ms |
52032 KB |
Output is correct |
48 |
Correct |
515 ms |
53052 KB |
Output is correct |
49 |
Correct |
6 ms |
1016 KB |
Output is correct |
50 |
Correct |
6 ms |
1016 KB |
Output is correct |
51 |
Correct |
4 ms |
920 KB |
Output is correct |
52 |
Correct |
2 ms |
376 KB |
Output is correct |
53 |
Correct |
6 ms |
1016 KB |
Output is correct |
54 |
Correct |
6 ms |
1016 KB |
Output is correct |
55 |
Correct |
6 ms |
1016 KB |
Output is correct |
56 |
Correct |
6 ms |
1016 KB |
Output is correct |
57 |
Correct |
6 ms |
1016 KB |
Output is correct |
58 |
Correct |
4 ms |
636 KB |
Output is correct |
59 |
Correct |
4 ms |
888 KB |
Output is correct |
60 |
Correct |
2 ms |
380 KB |
Output is correct |
61 |
Correct |
2185 ms |
253200 KB |
Output is correct |
62 |
Execution timed out |
5101 ms |
495096 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |