# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
156307 |
2019-10-05T02:17:20 Z |
wilwxk |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
515016 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2503;
int v[MAXN][MAXN];
short limite[MAXN][MAXN][4];
short qv[MAXN][MAXN][4];
short seg[4][MAXN][4*MAXN];
set<tuple<int, int, int, int> > respf;
int n, m;
void histoi() {
for(int i=0; i<n; i++) {
stack<pair<int, int> > st;
for(int j=0; j<m; j++) {
while(st.size()&&st.top().first<v[i][j]) {
qv[i][st.top().second][0]=j;
st.pop();
}
limite[i][j][2]= st.size() ? st.top().second : -1;
st.push({v[i][j], j});
}
while(st.size()) st.pop();
for(int j=m-1; j>=0; j--) {
while(st.size()&&st.top().first<v[i][j]) {
qv[i][st.top().second][2]=j;
st.pop();
}
limite[i][j][0]= st.size() ? st.top().second : m;
st.push({v[i][j], j});
}
}
}
void histoj() {
for(int j=0; j<m; j++) {
stack<pair<int, int> > st;
for(int i=0; i<n; i++) {
while(st.size()&&st.top().first<v[i][j]) {
qv[st.top().second][j][3]=i;
st.pop();
}
limite[i][j][1]= st.size() ? st.top().second : -1;
st.push({v[i][j], i});
}
while(st.size()) st.pop();
for(int i=n-1; i>=0; i--) {
while(st.size()&&st.top().first<v[i][j]) {
qv[st.top().second][j][1]=i;
st.pop();
}
limite[i][j][3]= st.size() ? st.top().second : n;
st.push({v[i][j], i});
}
}
}
void junta(int sind, int e, int d, int k, int k2) {
if(k==0||k==3) seg[k][k2][sind]=min(seg[k][k2][e], seg[k][k2][d]);
else seg[k][k2][sind]=max(seg[k][k2][e], seg[k][k2][d]);
}
void build(int sind, int ini, int fim, int k, int k2) {
if(ini==fim) {
if(k==0||k==2) seg[k][k2][sind]=limite[ini][k2][k];
else seg[k][k2][sind]=limite[k2][ini][k];
return;
}
int mid=(ini+fim)/2;
int e=sind*2; int d=e+1;
build(e, ini, mid, k, k2); build(d, mid+1, fim, k, k2);
junta(sind, e, d, k, k2);
}
void query(int sind, int ini, int fim, int qini, int qfim, int k, int k2) {
if(sind==1) {
if(k==0||k==3) seg[k][k2][0]=MAXN;
else seg[k][k2][0]=-1;
}
if(qini<=ini&&qfim>=fim) {
junta(0, 0, sind, k, k2);
return;
}
int mid=(ini+fim)/2;
int e=sind*2; int d=e+1;
if(qini<=mid) query(e, ini, mid, qini, qfim, k, k2);
if(qfim>mid) query(d, mid+1, fim, qini, qfim, k, k2);
}
bool checa(int a, int b, int c, int d) {
int i, j, i2, j2;
i=min(a, c); i2=max(a, c);
j=min(b, d); j2=max(b, d);
if(i<0||j<0||i2>n-1||j2>m-1) return 0;
// printf("checa %d %d %d %d\n", i, j, i2, j2);
query(1, 0, m-1, j+1, j2-1, 3, i);
int aa=seg[3][i][0];
if(aa<i2) return 0;
query(1, 0, m-1, j+1, j2-1, 1, i2);
int bb=seg[1][i2][0];
if(bb>i) return 0;
query(1, 0, n-1, i+1, i2-1, 0, j);
int cc=seg[0][j][0];
if(cc<j2) return 0;
query(1, 0, n-1, i+1, i2-1, 2, j2);
int dd=seg[2][j2][0];
if(dd>j) return 0;
// printf("ok %d %d %d %d\n", aa, bb, cc, dd);
return 1;
}
ll count_rectangles(vector< vector<int> > A) {
n=A.size(); m=A[0].size();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
v[i][j]=A[i][j];
qv[i][j][0]=m;
qv[i][j][1]=-1;
qv[i][j][2]=-1;
qv[i][j][3]=n;
}
}
histoi(); histoj();
// for(int i=0; i<n; i++) {
// for(int j=0; j<m; j++) printf("%d ", qv[i][j][0]);
// printf("\n");
// }
for(int i=0; i<n; i++) build(1, 0, m-1, 1, i), build(1, 0, m-1, 3, i);
for(int j=0; j<m; j++) build(1, 0, n-1, 0, j), build(1, 0, n-1, 2, j);
for(int ii=1; ii<n-1; ii++) {
for(int jj=1; jj<m-1; jj++) {
// printf("%d %d\n", ii, jj);
int i=qv[ii][jj][1];
int j=qv[ii][jj][2];
int i2=qv[ii][jj][3];
int j2=qv[ii][jj][0];
if(checa(i, j, i2, j2)) respf.insert({i, j, i2, j2});
}
}
return respf.size();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1016 KB |
Output is correct |
8 |
Correct |
3 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
1272 KB |
Output is correct |
10 |
Correct |
3 ms |
1272 KB |
Output is correct |
11 |
Correct |
3 ms |
1272 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 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 |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
4 ms |
1272 KB |
Output is correct |
20 |
Correct |
3 ms |
1144 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1016 KB |
Output is correct |
8 |
Correct |
3 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
1272 KB |
Output is correct |
10 |
Correct |
3 ms |
1272 KB |
Output is correct |
11 |
Correct |
3 ms |
1272 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 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 |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
10 ms |
3320 KB |
Output is correct |
18 |
Correct |
10 ms |
3448 KB |
Output is correct |
19 |
Correct |
9 ms |
3320 KB |
Output is correct |
20 |
Correct |
3 ms |
2936 KB |
Output is correct |
21 |
Correct |
8 ms |
3064 KB |
Output is correct |
22 |
Correct |
15 ms |
3064 KB |
Output is correct |
23 |
Correct |
7 ms |
3064 KB |
Output is correct |
24 |
Correct |
10 ms |
2552 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
4 ms |
1272 KB |
Output is correct |
28 |
Correct |
3 ms |
1144 KB |
Output is correct |
29 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1016 KB |
Output is correct |
8 |
Correct |
3 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
1272 KB |
Output is correct |
10 |
Correct |
3 ms |
1272 KB |
Output is correct |
11 |
Correct |
3 ms |
1272 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 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 |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
10 ms |
3320 KB |
Output is correct |
18 |
Correct |
10 ms |
3448 KB |
Output is correct |
19 |
Correct |
9 ms |
3320 KB |
Output is correct |
20 |
Correct |
3 ms |
2936 KB |
Output is correct |
21 |
Correct |
8 ms |
3064 KB |
Output is correct |
22 |
Correct |
15 ms |
3064 KB |
Output is correct |
23 |
Correct |
7 ms |
3064 KB |
Output is correct |
24 |
Correct |
10 ms |
2552 KB |
Output is correct |
25 |
Correct |
52 ms |
10524 KB |
Output is correct |
26 |
Correct |
51 ms |
10524 KB |
Output is correct |
27 |
Correct |
53 ms |
10616 KB |
Output is correct |
28 |
Correct |
24 ms |
8184 KB |
Output is correct |
29 |
Correct |
30 ms |
8824 KB |
Output is correct |
30 |
Correct |
27 ms |
8952 KB |
Output is correct |
31 |
Correct |
34 ms |
8952 KB |
Output is correct |
32 |
Correct |
34 ms |
8952 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
4 ms |
1272 KB |
Output is correct |
36 |
Correct |
3 ms |
1144 KB |
Output is correct |
37 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1016 KB |
Output is correct |
8 |
Correct |
3 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
1272 KB |
Output is correct |
10 |
Correct |
3 ms |
1272 KB |
Output is correct |
11 |
Correct |
3 ms |
1272 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 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 |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
10 ms |
3320 KB |
Output is correct |
18 |
Correct |
10 ms |
3448 KB |
Output is correct |
19 |
Correct |
9 ms |
3320 KB |
Output is correct |
20 |
Correct |
3 ms |
2936 KB |
Output is correct |
21 |
Correct |
8 ms |
3064 KB |
Output is correct |
22 |
Correct |
15 ms |
3064 KB |
Output is correct |
23 |
Correct |
7 ms |
3064 KB |
Output is correct |
24 |
Correct |
10 ms |
2552 KB |
Output is correct |
25 |
Correct |
52 ms |
10524 KB |
Output is correct |
26 |
Correct |
51 ms |
10524 KB |
Output is correct |
27 |
Correct |
53 ms |
10616 KB |
Output is correct |
28 |
Correct |
24 ms |
8184 KB |
Output is correct |
29 |
Correct |
30 ms |
8824 KB |
Output is correct |
30 |
Correct |
27 ms |
8952 KB |
Output is correct |
31 |
Correct |
34 ms |
8952 KB |
Output is correct |
32 |
Correct |
34 ms |
8952 KB |
Output is correct |
33 |
Correct |
194 ms |
47964 KB |
Output is correct |
34 |
Correct |
186 ms |
48088 KB |
Output is correct |
35 |
Correct |
179 ms |
48036 KB |
Output is correct |
36 |
Correct |
179 ms |
48036 KB |
Output is correct |
37 |
Correct |
774 ms |
78504 KB |
Output is correct |
38 |
Correct |
761 ms |
78568 KB |
Output is correct |
39 |
Correct |
776 ms |
78852 KB |
Output is correct |
40 |
Correct |
673 ms |
74588 KB |
Output is correct |
41 |
Correct |
199 ms |
46948 KB |
Output is correct |
42 |
Correct |
237 ms |
48760 KB |
Output is correct |
43 |
Correct |
332 ms |
57024 KB |
Output is correct |
44 |
Correct |
340 ms |
58956 KB |
Output is correct |
45 |
Correct |
185 ms |
36792 KB |
Output is correct |
46 |
Correct |
161 ms |
32480 KB |
Output is correct |
47 |
Correct |
386 ms |
57904 KB |
Output is correct |
48 |
Correct |
388 ms |
58968 KB |
Output is correct |
49 |
Correct |
2 ms |
376 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
4 ms |
1272 KB |
Output is correct |
52 |
Correct |
3 ms |
1144 KB |
Output is correct |
53 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
21112 KB |
Output is correct |
2 |
Correct |
18 ms |
17912 KB |
Output is correct |
3 |
Correct |
18 ms |
20856 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
23 ms |
20984 KB |
Output is correct |
6 |
Correct |
20 ms |
20984 KB |
Output is correct |
7 |
Correct |
34 ms |
20984 KB |
Output is correct |
8 |
Correct |
22 ms |
20956 KB |
Output is correct |
9 |
Correct |
23 ms |
20984 KB |
Output is correct |
10 |
Correct |
18 ms |
20600 KB |
Output is correct |
11 |
Correct |
19 ms |
20856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
1291 ms |
200236 KB |
Output is correct |
3 |
Correct |
2937 ms |
394276 KB |
Output is correct |
4 |
Correct |
2858 ms |
395968 KB |
Output is correct |
5 |
Correct |
2820 ms |
395904 KB |
Output is correct |
6 |
Correct |
830 ms |
199616 KB |
Output is correct |
7 |
Correct |
1701 ms |
370236 KB |
Output is correct |
8 |
Correct |
1771 ms |
380284 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
4 ms |
1272 KB |
Output is correct |
12 |
Correct |
3 ms |
1144 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1016 KB |
Output is correct |
8 |
Correct |
3 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
1272 KB |
Output is correct |
10 |
Correct |
3 ms |
1272 KB |
Output is correct |
11 |
Correct |
3 ms |
1272 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 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 |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
10 ms |
3320 KB |
Output is correct |
18 |
Correct |
10 ms |
3448 KB |
Output is correct |
19 |
Correct |
9 ms |
3320 KB |
Output is correct |
20 |
Correct |
3 ms |
2936 KB |
Output is correct |
21 |
Correct |
8 ms |
3064 KB |
Output is correct |
22 |
Correct |
15 ms |
3064 KB |
Output is correct |
23 |
Correct |
7 ms |
3064 KB |
Output is correct |
24 |
Correct |
10 ms |
2552 KB |
Output is correct |
25 |
Correct |
52 ms |
10524 KB |
Output is correct |
26 |
Correct |
51 ms |
10524 KB |
Output is correct |
27 |
Correct |
53 ms |
10616 KB |
Output is correct |
28 |
Correct |
24 ms |
8184 KB |
Output is correct |
29 |
Correct |
30 ms |
8824 KB |
Output is correct |
30 |
Correct |
27 ms |
8952 KB |
Output is correct |
31 |
Correct |
34 ms |
8952 KB |
Output is correct |
32 |
Correct |
34 ms |
8952 KB |
Output is correct |
33 |
Correct |
194 ms |
47964 KB |
Output is correct |
34 |
Correct |
186 ms |
48088 KB |
Output is correct |
35 |
Correct |
179 ms |
48036 KB |
Output is correct |
36 |
Correct |
179 ms |
48036 KB |
Output is correct |
37 |
Correct |
774 ms |
78504 KB |
Output is correct |
38 |
Correct |
761 ms |
78568 KB |
Output is correct |
39 |
Correct |
776 ms |
78852 KB |
Output is correct |
40 |
Correct |
673 ms |
74588 KB |
Output is correct |
41 |
Correct |
199 ms |
46948 KB |
Output is correct |
42 |
Correct |
237 ms |
48760 KB |
Output is correct |
43 |
Correct |
332 ms |
57024 KB |
Output is correct |
44 |
Correct |
340 ms |
58956 KB |
Output is correct |
45 |
Correct |
185 ms |
36792 KB |
Output is correct |
46 |
Correct |
161 ms |
32480 KB |
Output is correct |
47 |
Correct |
386 ms |
57904 KB |
Output is correct |
48 |
Correct |
388 ms |
58968 KB |
Output is correct |
49 |
Correct |
21 ms |
21112 KB |
Output is correct |
50 |
Correct |
18 ms |
17912 KB |
Output is correct |
51 |
Correct |
18 ms |
20856 KB |
Output is correct |
52 |
Correct |
2 ms |
376 KB |
Output is correct |
53 |
Correct |
23 ms |
20984 KB |
Output is correct |
54 |
Correct |
20 ms |
20984 KB |
Output is correct |
55 |
Correct |
34 ms |
20984 KB |
Output is correct |
56 |
Correct |
22 ms |
20956 KB |
Output is correct |
57 |
Correct |
23 ms |
20984 KB |
Output is correct |
58 |
Correct |
18 ms |
20600 KB |
Output is correct |
59 |
Correct |
19 ms |
20856 KB |
Output is correct |
60 |
Correct |
2 ms |
632 KB |
Output is correct |
61 |
Correct |
1291 ms |
200236 KB |
Output is correct |
62 |
Correct |
2937 ms |
394276 KB |
Output is correct |
63 |
Correct |
2858 ms |
395968 KB |
Output is correct |
64 |
Correct |
2820 ms |
395904 KB |
Output is correct |
65 |
Correct |
830 ms |
199616 KB |
Output is correct |
66 |
Correct |
1701 ms |
370236 KB |
Output is correct |
67 |
Correct |
1771 ms |
380284 KB |
Output is correct |
68 |
Correct |
2208 ms |
399708 KB |
Output is correct |
69 |
Correct |
2361 ms |
391704 KB |
Output is correct |
70 |
Correct |
2225 ms |
391600 KB |
Output is correct |
71 |
Correct |
2254 ms |
391684 KB |
Output is correct |
72 |
Execution timed out |
5114 ms |
515016 KB |
Time limit exceeded |
73 |
Halted |
0 ms |
0 KB |
- |