# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
295324 |
2020-09-09T15:37:10 Z |
Atill83 |
Rectangles (IOI19_rect) |
C++14 |
|
1008 ms |
463224 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = (int) 205;
bool hori[MAXN][MAXN][MAXN], verti[MAXN][MAXN][MAXN];
int ph[MAXN][MAXN][MAXN], pv[MAXN][MAXN][MAXN];
int nx[2505];
ll pre[2505][2505];
bool visited[2505][2505];
int mxx[4'250'050], mxy[4'250'050], mnx[4'250'050], mny[4'250'050];
int cc = 0;
void dfs(int i, int j, vector<vector<int>> &vc){
if(i < 0 || i >= vc.size() || j < 0 || j >= vc[0].size() || vc[i][j] == 1){
return;
}
if(visited[i][j]) return;
visited[i][j] = 1;
mnx[cc] = min(mnx[cc], i);
mxx[cc] = max(mxx[cc], i);
mny[cc] = min(mny[cc], j);
mxy[cc] = max(mxy[cc], j);
dfs(i + 1, j, vc);
dfs(i - 1, j, vc);
dfs(i, j + 1, vc);
dfs(i, j - 1, vc);
}
int gtpre(int x1, int y1, int x2, int y2){
if(x1 == 0 && y1 == 0){
return pre[x2][y2];
}else if(x1 == 0){
return pre[x2][y2] - pre[x2][y1 - 1];
}else if(y1 == 0){
return pre[x2][y2] - pre[x1 - 1][y2];
}else{
return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
}
}
long long count_rectangles(vector<vector<int>> a) {
ll ans = 0;
int n = a.size();
int m = a[0].size();
if(n <= 200 && m <= 200){
for(int i = 0; i < n; i++){
for(int j = 0; j + 1 < m; j++){
int mx = a[i][j + 1];
for(int l = j + 2; l < m; l++){
hori[i][j][l] = (min(a[i][l], a[i][j]) > mx);
mx = max(mx, a[i][l]);
if(mx > a[i][j]) break;
}
}
}
for(int j = 0; j < m; j++){
for(int i = 0; i + 1 < n; i++){
int mx = a[i + 1][j];
for(int k = i + 2; k < n; k++){
verti[i][j][k] = (min(a[k][j] , a[i][j]) > mx);
mx = max(mx, a[k][j]);
if(mx > a[i][j]) break;
}
}
}
for(int l = 3; l <= m; l++){
for(int j = 0; j <= m - l; j++){
for(int i = 0; i < n; i++){
int pre = (i == 0 ? 0 : ph[i - 1][j][l]);
ph[i][j][l] = pre + hori[i][j][j + l - 1];
}
}
}
for(int l = 3; l <= n; l++){
for(int i = 0; i <= n - l; i++){
for(int j = 0; j < m; j++){
int pre = (j == 0 ? 0 : pv[i][j - 1][l]);
pv[i][j][l] = pre + verti[i][j][i + l - 1];
}
}
}
for(int i = 0; i < n - 2; i++){
for(int j = 0; j < m - 2; j++){
for(int k = i + 2; k < n; k++){
for(int l = j + 2; l < m; l++){
int d1 = -ph[i][j][l - j + 1] + ph[k - 1][j][l - j + 1];
int d2 = -pv[i][j][k - i + 1] + pv[i][l - 1][k - i + 1];
if(d1 == k - i - 1 && d2 == l - j - 1)
ans++;
}
}
}
}
return ans;
}else if(n <= 3){
if(n <= 2) return 0;
ll ans = 0;
vector<pair<int, int>> ara;
int lastl = 0;
for(int i = 1; i < m - 1; i++){
if(min(a[0][i], a[2][i]) <= a[1][i]){
if(lastl != i - 1);
ara.push_back({lastl, i});
lastl = i;
}
}
if(lastl != m - 2) ara.push_back({lastl, m - 1});
for(auto u: ara){
int l = u.first, r = u.second;
stack<int> st;
for(int j = r; j >= l; j--){
while(!st.empty() && a[1][st.top()] <= a[1][j])
st.pop();
if(st.empty()){
nx[j] = r + 1;
}else{
nx[j] = st.top();
}
st.push(j);
}
for(int j = l; j < r - 1; j++){
int mx = a[1][j + 1];
int rr = nx[j + 1];
//cerr<<j<<" "<<r<<"\n";
//cerr<<a[1][j + 1]<<" "<<a[1][j]<<" "<<a[1][rr]<<endl;
while(rr <= r){
if(mx >= min(a[1][j], a[1][rr]))
break;
ans++;
mx = max(mx, a[1][rr]);
rr = nx[rr];
//cerr<<rr<<" ";
}
}
}
return ans;
}else{
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i == 0 && j == 0) pre[i][j] = a[i][j];
else if(i == 0) pre[i][j] = pre[i][j - 1] + a[i][j];
else if(j == 0) pre[i][j] = pre[i - 1][j] + a[i][j];
else pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + a[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(visited[i][j] || a[i][j] == 1){
continue;
}
mnx[cc] = mxx[cc] = i;
mny[cc] = mxy[cc] = j;
dfs(i, j, a);
int say = gtpre(mnx[cc], mny[cc], mxx[cc], mxy[cc]);
if(say == 0 && mnx[cc] != 0 && mny[cc] != 0 && mxx[cc] != n - 1 && mxy[cc] != m - 1)
ans++;
cc++;
}
}
return ans;
}
}
Compilation message
rect.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&)':
rect.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | if(i < 0 || i >= vc.size() || j < 0 || j >= vc[0].size() || vc[i][j] == 1){
| ~~^~~~~~~~~~~~
rect.cpp:15:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | if(i < 0 || i >= vc.size() || j < 0 || j >= vc[0].size() || vc[i][j] == 1){
| ~~^~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:109:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
109 | if(lastl != i - 1);
| ^~
rect.cpp:110:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
110 | ara.push_back({lastl, i});
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
2432 KB |
Output is correct |
3 |
Correct |
2 ms |
2432 KB |
Output is correct |
4 |
Correct |
3 ms |
2432 KB |
Output is correct |
5 |
Correct |
2 ms |
2432 KB |
Output is correct |
6 |
Correct |
2 ms |
2432 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
1152 KB |
Output is correct |
9 |
Correct |
2 ms |
2432 KB |
Output is correct |
10 |
Correct |
2 ms |
2432 KB |
Output is correct |
11 |
Correct |
2 ms |
2432 KB |
Output is correct |
12 |
Correct |
3 ms |
2432 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
640 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
2432 KB |
Output is correct |
20 |
Correct |
1 ms |
1536 KB |
Output is correct |
21 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
2432 KB |
Output is correct |
3 |
Correct |
2 ms |
2432 KB |
Output is correct |
4 |
Correct |
3 ms |
2432 KB |
Output is correct |
5 |
Correct |
2 ms |
2432 KB |
Output is correct |
6 |
Correct |
2 ms |
2432 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
1152 KB |
Output is correct |
9 |
Correct |
2 ms |
2432 KB |
Output is correct |
10 |
Correct |
2 ms |
2432 KB |
Output is correct |
11 |
Correct |
2 ms |
2432 KB |
Output is correct |
12 |
Correct |
3 ms |
2432 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
640 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
32 ms |
14080 KB |
Output is correct |
18 |
Correct |
33 ms |
14208 KB |
Output is correct |
19 |
Correct |
33 ms |
14080 KB |
Output is correct |
20 |
Correct |
32 ms |
14080 KB |
Output is correct |
21 |
Correct |
30 ms |
13928 KB |
Output is correct |
22 |
Correct |
36 ms |
13952 KB |
Output is correct |
23 |
Correct |
32 ms |
14080 KB |
Output is correct |
24 |
Correct |
10 ms |
7680 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
0 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
2432 KB |
Output is correct |
28 |
Correct |
1 ms |
1536 KB |
Output is correct |
29 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
2432 KB |
Output is correct |
3 |
Correct |
2 ms |
2432 KB |
Output is correct |
4 |
Correct |
3 ms |
2432 KB |
Output is correct |
5 |
Correct |
2 ms |
2432 KB |
Output is correct |
6 |
Correct |
2 ms |
2432 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
1152 KB |
Output is correct |
9 |
Correct |
2 ms |
2432 KB |
Output is correct |
10 |
Correct |
2 ms |
2432 KB |
Output is correct |
11 |
Correct |
2 ms |
2432 KB |
Output is correct |
12 |
Correct |
3 ms |
2432 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
640 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
32 ms |
14080 KB |
Output is correct |
18 |
Correct |
33 ms |
14208 KB |
Output is correct |
19 |
Correct |
33 ms |
14080 KB |
Output is correct |
20 |
Correct |
32 ms |
14080 KB |
Output is correct |
21 |
Correct |
30 ms |
13928 KB |
Output is correct |
22 |
Correct |
36 ms |
13952 KB |
Output is correct |
23 |
Correct |
32 ms |
14080 KB |
Output is correct |
24 |
Correct |
10 ms |
7680 KB |
Output is correct |
25 |
Correct |
1002 ms |
82052 KB |
Output is correct |
26 |
Correct |
1008 ms |
82168 KB |
Output is correct |
27 |
Correct |
1000 ms |
82040 KB |
Output is correct |
28 |
Correct |
980 ms |
82040 KB |
Output is correct |
29 |
Correct |
969 ms |
82040 KB |
Output is correct |
30 |
Correct |
981 ms |
82040 KB |
Output is correct |
31 |
Correct |
984 ms |
82040 KB |
Output is correct |
32 |
Correct |
954 ms |
81016 KB |
Output is correct |
33 |
Correct |
0 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
2432 KB |
Output is correct |
36 |
Correct |
1 ms |
1536 KB |
Output is correct |
37 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
2432 KB |
Output is correct |
3 |
Correct |
2 ms |
2432 KB |
Output is correct |
4 |
Correct |
3 ms |
2432 KB |
Output is correct |
5 |
Correct |
2 ms |
2432 KB |
Output is correct |
6 |
Correct |
2 ms |
2432 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
1152 KB |
Output is correct |
9 |
Correct |
2 ms |
2432 KB |
Output is correct |
10 |
Correct |
2 ms |
2432 KB |
Output is correct |
11 |
Correct |
2 ms |
2432 KB |
Output is correct |
12 |
Correct |
3 ms |
2432 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
640 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
32 ms |
14080 KB |
Output is correct |
18 |
Correct |
33 ms |
14208 KB |
Output is correct |
19 |
Correct |
33 ms |
14080 KB |
Output is correct |
20 |
Correct |
32 ms |
14080 KB |
Output is correct |
21 |
Correct |
30 ms |
13928 KB |
Output is correct |
22 |
Correct |
36 ms |
13952 KB |
Output is correct |
23 |
Correct |
32 ms |
14080 KB |
Output is correct |
24 |
Correct |
10 ms |
7680 KB |
Output is correct |
25 |
Correct |
1002 ms |
82052 KB |
Output is correct |
26 |
Correct |
1008 ms |
82168 KB |
Output is correct |
27 |
Correct |
1000 ms |
82040 KB |
Output is correct |
28 |
Correct |
980 ms |
82040 KB |
Output is correct |
29 |
Correct |
969 ms |
82040 KB |
Output is correct |
30 |
Correct |
981 ms |
82040 KB |
Output is correct |
31 |
Correct |
984 ms |
82040 KB |
Output is correct |
32 |
Correct |
954 ms |
81016 KB |
Output is correct |
33 |
Incorrect |
59 ms |
43180 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
416 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
155 ms |
53368 KB |
Output is correct |
3 |
Correct |
329 ms |
119032 KB |
Output is correct |
4 |
Correct |
334 ms |
119544 KB |
Output is correct |
5 |
Correct |
348 ms |
119580 KB |
Output is correct |
6 |
Correct |
321 ms |
170616 KB |
Output is correct |
7 |
Correct |
706 ms |
397688 KB |
Output is correct |
8 |
Correct |
809 ms |
463224 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
2432 KB |
Output is correct |
12 |
Correct |
1 ms |
1536 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
2432 KB |
Output is correct |
3 |
Correct |
2 ms |
2432 KB |
Output is correct |
4 |
Correct |
3 ms |
2432 KB |
Output is correct |
5 |
Correct |
2 ms |
2432 KB |
Output is correct |
6 |
Correct |
2 ms |
2432 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
1152 KB |
Output is correct |
9 |
Correct |
2 ms |
2432 KB |
Output is correct |
10 |
Correct |
2 ms |
2432 KB |
Output is correct |
11 |
Correct |
2 ms |
2432 KB |
Output is correct |
12 |
Correct |
3 ms |
2432 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
640 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
32 ms |
14080 KB |
Output is correct |
18 |
Correct |
33 ms |
14208 KB |
Output is correct |
19 |
Correct |
33 ms |
14080 KB |
Output is correct |
20 |
Correct |
32 ms |
14080 KB |
Output is correct |
21 |
Correct |
30 ms |
13928 KB |
Output is correct |
22 |
Correct |
36 ms |
13952 KB |
Output is correct |
23 |
Correct |
32 ms |
14080 KB |
Output is correct |
24 |
Correct |
10 ms |
7680 KB |
Output is correct |
25 |
Correct |
1002 ms |
82052 KB |
Output is correct |
26 |
Correct |
1008 ms |
82168 KB |
Output is correct |
27 |
Correct |
1000 ms |
82040 KB |
Output is correct |
28 |
Correct |
980 ms |
82040 KB |
Output is correct |
29 |
Correct |
969 ms |
82040 KB |
Output is correct |
30 |
Correct |
981 ms |
82040 KB |
Output is correct |
31 |
Correct |
984 ms |
82040 KB |
Output is correct |
32 |
Correct |
954 ms |
81016 KB |
Output is correct |
33 |
Incorrect |
59 ms |
43180 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |