# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
824999 |
2023-08-14T13:02:39 Z |
Ronin13 |
Rectangles (IOI19_rect) |
C++17 |
|
5000 ms |
805872 KB |
#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 2501;
int c[nmax][nmax];// for min
int d[nmax][nmax];// for max
int st[nmax][nmax][13][2];
int get_max(int ind, int l, int r){
int len = r - l + 1;
int x = log2(len);
return max(st[ind][l][x][0], st[ind][max(0,r - (1 << x) + 1)][x][0]);
}
int get_mn(int ind, int l, int r){
int len = r - l + 1;
int x = log2(len);
return min(st[ind][l][x][1], st[ind][max(0, r - (1 << x) + 1)][x][1]);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size(), m = a[0].size();
for(int i = 0; i < n; i++){
stack <int> st;
for(int j = 0; j < m; j++){
while(!st.empty()){
if(a[i][st.top()] < a[i][j]) st.pop();
else break;
}
if(!st.empty())
d[i][j] = st.top();
st.push(j);
}
while(!st.empty()){
st.pop();
}
for(int j= m - 1 ;j >= 0; j--){
while(!st.empty()){
if(a[i][st.top()] < a[i][j]) st.pop();
else break;
}
if(!st.empty()) c[i][j] = st.top();
else c[i][j] = m - 1;
st.push(j);
}
}
for(int i = 0; i < m; i++){
for(int j = n - 1; j >= 0; j--){
st[i][j][0][0] = d[j][i], st[i][j][0][1] = c[j][i];
for(int x =1; x < 13; x++){
st[i][j][x][0] = max(st[i][j][x - 1][0],
st[i][min(j + (1 << (x - 1)), n - 1)][x - 1][0]);
st[i][j][x][1] = min(st[i][j][x - 1][1],
st[i][min(j + (1 << (x - 1)), n - 1)][x - 1][1]);
}
}
}
vector <pii> p[m + 1];
for(int j = 0; j < m; j++){
int l[n + 1], r[n + 1];
fill(l , l + n + 1, -1);
fill(r, r + n + 1, n + 1);
stack <int> st;
for(int i = 0; i < n; i++){
while(!st.empty()){
if(a[st.top()][j] > a[i][j]) break;
else st.pop();
}
if(!st.empty()) l[i] = st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n - 1; i >= 0; i--){
while(!st.empty()){
if(a[st.top()][j] > a[i][j]) break;
else st.pop();
}
if(!st.empty()) r[i] = st.top();
st.push(i);
}
for(int i = 0; i < n; i++){
if(l[i] != -1 && r[i] != n + 1)
p[j].pb({l[i] + 1, r[i] - 1});
}
sort(p[j].begin(), p[j].end());
p[j].erase(unique(p[j].begin(), p[j].end()), p[j].end());
}
int ans = 0;
for(int i = 1; i < m - 1; i++){
vector <pii> cur = p[i];
vector <pii> nw;
for(int j = i; j < m - 1; j++){
int inda = 0, indb = 0;
while(inda < cur.size() && indb < p[j].size()){
if(cur[inda] == p[j][indb]) nw.pb(cur[inda]), inda++, indb++;
else{
if(cur[inda] < p[j][indb]) inda++;
else indb++;
}
}
swap(nw, cur);
nw.clear();
for(auto to : cur){
//if(i == 3 && j == 3) cout << to.f << ' ' << to.s << "\n";
int L = to.f, R = to.s;
if(get_max(j + 1, L, R) >= i) continue;
// if(i == 3 && j == 3) cout << to.f << ' ' << to.s << "\n";
// cout << get_mn(i - 1, L, R) << "\n";
if(get_mn(i - 1, L, R) <= j) continue;
// cout << i << ' ' << j << ' ' << L << ' ' << R << "\n";
ans++;
}
}
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:106:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while(inda < cur.size() && indb < p[j].size()){
| ~~~~~^~~~~~~~~~~~
rect.cpp:106:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while(inda < cur.size() && indb < p[j].size()){
| ~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
820 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
0 ms |
304 KB |
Output is correct |
19 |
Correct |
1 ms |
812 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
820 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
0 ms |
304 KB |
Output is correct |
19 |
Correct |
1 ms |
812 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
6 ms |
2132 KB |
Output is correct |
23 |
Correct |
6 ms |
2132 KB |
Output is correct |
24 |
Correct |
6 ms |
2132 KB |
Output is correct |
25 |
Correct |
2 ms |
2132 KB |
Output is correct |
26 |
Correct |
3 ms |
2084 KB |
Output is correct |
27 |
Correct |
2 ms |
2132 KB |
Output is correct |
28 |
Correct |
2 ms |
2132 KB |
Output is correct |
29 |
Correct |
1 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
820 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
6 ms |
2132 KB |
Output is correct |
18 |
Correct |
6 ms |
2132 KB |
Output is correct |
19 |
Correct |
6 ms |
2132 KB |
Output is correct |
20 |
Correct |
2 ms |
2132 KB |
Output is correct |
21 |
Correct |
3 ms |
2084 KB |
Output is correct |
22 |
Correct |
2 ms |
2132 KB |
Output is correct |
23 |
Correct |
2 ms |
2132 KB |
Output is correct |
24 |
Correct |
1 ms |
1492 KB |
Output is correct |
25 |
Correct |
1 ms |
308 KB |
Output is correct |
26 |
Correct |
0 ms |
304 KB |
Output is correct |
27 |
Correct |
1 ms |
812 KB |
Output is correct |
28 |
Correct |
1 ms |
596 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
74 ms |
8040 KB |
Output is correct |
31 |
Correct |
69 ms |
7944 KB |
Output is correct |
32 |
Correct |
73 ms |
8044 KB |
Output is correct |
33 |
Correct |
8 ms |
7892 KB |
Output is correct |
34 |
Correct |
12 ms |
8020 KB |
Output is correct |
35 |
Correct |
13 ms |
8020 KB |
Output is correct |
36 |
Correct |
14 ms |
8020 KB |
Output is correct |
37 |
Correct |
13 ms |
7944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
820 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
6 ms |
2132 KB |
Output is correct |
18 |
Correct |
6 ms |
2132 KB |
Output is correct |
19 |
Correct |
6 ms |
2132 KB |
Output is correct |
20 |
Correct |
2 ms |
2132 KB |
Output is correct |
21 |
Correct |
3 ms |
2084 KB |
Output is correct |
22 |
Correct |
2 ms |
2132 KB |
Output is correct |
23 |
Correct |
2 ms |
2132 KB |
Output is correct |
24 |
Correct |
1 ms |
1492 KB |
Output is correct |
25 |
Correct |
74 ms |
8040 KB |
Output is correct |
26 |
Correct |
69 ms |
7944 KB |
Output is correct |
27 |
Correct |
73 ms |
8044 KB |
Output is correct |
28 |
Correct |
8 ms |
7892 KB |
Output is correct |
29 |
Correct |
12 ms |
8020 KB |
Output is correct |
30 |
Correct |
13 ms |
8020 KB |
Output is correct |
31 |
Correct |
14 ms |
8020 KB |
Output is correct |
32 |
Correct |
13 ms |
7944 KB |
Output is correct |
33 |
Correct |
1 ms |
308 KB |
Output is correct |
34 |
Correct |
0 ms |
304 KB |
Output is correct |
35 |
Correct |
1 ms |
812 KB |
Output is correct |
36 |
Correct |
1 ms |
596 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
79 ms |
68528 KB |
Output is correct |
39 |
Correct |
76 ms |
69500 KB |
Output is correct |
40 |
Correct |
77 ms |
68572 KB |
Output is correct |
41 |
Correct |
77 ms |
69444 KB |
Output is correct |
42 |
Correct |
3521 ms |
72248 KB |
Output is correct |
43 |
Correct |
3573 ms |
75320 KB |
Output is correct |
44 |
Correct |
3525 ms |
75676 KB |
Output is correct |
45 |
Correct |
3263 ms |
71552 KB |
Output is correct |
46 |
Correct |
96 ms |
70192 KB |
Output is correct |
47 |
Correct |
110 ms |
70180 KB |
Output is correct |
48 |
Correct |
145 ms |
74104 KB |
Output is correct |
49 |
Correct |
148 ms |
75724 KB |
Output is correct |
50 |
Correct |
72 ms |
40948 KB |
Output is correct |
51 |
Correct |
71 ms |
39508 KB |
Output is correct |
52 |
Correct |
325 ms |
74892 KB |
Output is correct |
53 |
Correct |
382 ms |
75820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
12628 KB |
Output is correct |
2 |
Correct |
38 ms |
10708 KB |
Output is correct |
3 |
Correct |
16 ms |
12520 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
12 ms |
12576 KB |
Output is correct |
6 |
Correct |
12 ms |
12576 KB |
Output is correct |
7 |
Correct |
12 ms |
12584 KB |
Output is correct |
8 |
Correct |
13 ms |
12500 KB |
Output is correct |
9 |
Correct |
16 ms |
12572 KB |
Output is correct |
10 |
Correct |
13 ms |
11860 KB |
Output is correct |
11 |
Correct |
12 ms |
12240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
0 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
812 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
432 KB |
Output is correct |
7 |
Correct |
584 ms |
367120 KB |
Output is correct |
8 |
Correct |
1421 ms |
768856 KB |
Output is correct |
9 |
Correct |
1339 ms |
769696 KB |
Output is correct |
10 |
Correct |
1365 ms |
769940 KB |
Output is correct |
11 |
Correct |
458 ms |
373584 KB |
Output is correct |
12 |
Correct |
842 ms |
692844 KB |
Output is correct |
13 |
Correct |
917 ms |
735468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
820 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
6 ms |
2132 KB |
Output is correct |
18 |
Correct |
6 ms |
2132 KB |
Output is correct |
19 |
Correct |
6 ms |
2132 KB |
Output is correct |
20 |
Correct |
2 ms |
2132 KB |
Output is correct |
21 |
Correct |
3 ms |
2084 KB |
Output is correct |
22 |
Correct |
2 ms |
2132 KB |
Output is correct |
23 |
Correct |
2 ms |
2132 KB |
Output is correct |
24 |
Correct |
1 ms |
1492 KB |
Output is correct |
25 |
Correct |
74 ms |
8040 KB |
Output is correct |
26 |
Correct |
69 ms |
7944 KB |
Output is correct |
27 |
Correct |
73 ms |
8044 KB |
Output is correct |
28 |
Correct |
8 ms |
7892 KB |
Output is correct |
29 |
Correct |
12 ms |
8020 KB |
Output is correct |
30 |
Correct |
13 ms |
8020 KB |
Output is correct |
31 |
Correct |
14 ms |
8020 KB |
Output is correct |
32 |
Correct |
13 ms |
7944 KB |
Output is correct |
33 |
Correct |
79 ms |
68528 KB |
Output is correct |
34 |
Correct |
76 ms |
69500 KB |
Output is correct |
35 |
Correct |
77 ms |
68572 KB |
Output is correct |
36 |
Correct |
77 ms |
69444 KB |
Output is correct |
37 |
Correct |
3521 ms |
72248 KB |
Output is correct |
38 |
Correct |
3573 ms |
75320 KB |
Output is correct |
39 |
Correct |
3525 ms |
75676 KB |
Output is correct |
40 |
Correct |
3263 ms |
71552 KB |
Output is correct |
41 |
Correct |
96 ms |
70192 KB |
Output is correct |
42 |
Correct |
110 ms |
70180 KB |
Output is correct |
43 |
Correct |
145 ms |
74104 KB |
Output is correct |
44 |
Correct |
148 ms |
75724 KB |
Output is correct |
45 |
Correct |
72 ms |
40948 KB |
Output is correct |
46 |
Correct |
71 ms |
39508 KB |
Output is correct |
47 |
Correct |
325 ms |
74892 KB |
Output is correct |
48 |
Correct |
382 ms |
75820 KB |
Output is correct |
49 |
Correct |
59 ms |
12628 KB |
Output is correct |
50 |
Correct |
38 ms |
10708 KB |
Output is correct |
51 |
Correct |
16 ms |
12520 KB |
Output is correct |
52 |
Correct |
1 ms |
212 KB |
Output is correct |
53 |
Correct |
12 ms |
12576 KB |
Output is correct |
54 |
Correct |
12 ms |
12576 KB |
Output is correct |
55 |
Correct |
12 ms |
12584 KB |
Output is correct |
56 |
Correct |
13 ms |
12500 KB |
Output is correct |
57 |
Correct |
16 ms |
12572 KB |
Output is correct |
58 |
Correct |
13 ms |
11860 KB |
Output is correct |
59 |
Correct |
12 ms |
12240 KB |
Output is correct |
60 |
Correct |
0 ms |
432 KB |
Output is correct |
61 |
Correct |
584 ms |
367120 KB |
Output is correct |
62 |
Correct |
1421 ms |
768856 KB |
Output is correct |
63 |
Correct |
1339 ms |
769696 KB |
Output is correct |
64 |
Correct |
1365 ms |
769940 KB |
Output is correct |
65 |
Correct |
458 ms |
373584 KB |
Output is correct |
66 |
Correct |
842 ms |
692844 KB |
Output is correct |
67 |
Correct |
917 ms |
735468 KB |
Output is correct |
68 |
Correct |
1 ms |
308 KB |
Output is correct |
69 |
Correct |
0 ms |
304 KB |
Output is correct |
70 |
Correct |
1 ms |
812 KB |
Output is correct |
71 |
Correct |
1 ms |
596 KB |
Output is correct |
72 |
Correct |
0 ms |
340 KB |
Output is correct |
73 |
Correct |
1197 ms |
768144 KB |
Output is correct |
74 |
Correct |
1201 ms |
775344 KB |
Output is correct |
75 |
Correct |
1202 ms |
771096 KB |
Output is correct |
76 |
Correct |
1193 ms |
775520 KB |
Output is correct |
77 |
Execution timed out |
5139 ms |
805872 KB |
Time limit exceeded |
78 |
Halted |
0 ms |
0 KB |
- |