# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
156311 |
2019-10-05T02:26:11 Z |
wilwxk |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
465160 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(respf.find({i, j, i2, j2})!=respf.end()) continue;
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 |
4 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
2 ms |
1020 KB |
Output is correct |
8 |
Correct |
2 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 |
1 ms |
1272 KB |
Output is correct |
12 |
Correct |
3 ms |
1272 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
632 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 |
3 ms |
1272 KB |
Output is correct |
20 |
Correct |
3 ms |
1148 KB |
Output is correct |
21 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
2 ms |
1020 KB |
Output is correct |
8 |
Correct |
2 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 |
1 ms |
1272 KB |
Output is correct |
12 |
Correct |
3 ms |
1272 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
9 ms |
3320 KB |
Output is correct |
18 |
Correct |
9 ms |
3320 KB |
Output is correct |
19 |
Correct |
9 ms |
3320 KB |
Output is correct |
20 |
Correct |
6 ms |
2936 KB |
Output is correct |
21 |
Correct |
7 ms |
3064 KB |
Output is correct |
22 |
Correct |
7 ms |
3064 KB |
Output is correct |
23 |
Correct |
7 ms |
3064 KB |
Output is correct |
24 |
Correct |
5 ms |
2424 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
1272 KB |
Output is correct |
28 |
Correct |
3 ms |
1148 KB |
Output is correct |
29 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
2 ms |
1020 KB |
Output is correct |
8 |
Correct |
2 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 |
1 ms |
1272 KB |
Output is correct |
12 |
Correct |
3 ms |
1272 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
9 ms |
3320 KB |
Output is correct |
18 |
Correct |
9 ms |
3320 KB |
Output is correct |
19 |
Correct |
9 ms |
3320 KB |
Output is correct |
20 |
Correct |
6 ms |
2936 KB |
Output is correct |
21 |
Correct |
7 ms |
3064 KB |
Output is correct |
22 |
Correct |
7 ms |
3064 KB |
Output is correct |
23 |
Correct |
7 ms |
3064 KB |
Output is correct |
24 |
Correct |
5 ms |
2424 KB |
Output is correct |
25 |
Correct |
54 ms |
10332 KB |
Output is correct |
26 |
Correct |
54 ms |
10332 KB |
Output is correct |
27 |
Correct |
55 ms |
10360 KB |
Output is correct |
28 |
Correct |
22 ms |
8056 KB |
Output is correct |
29 |
Correct |
30 ms |
8696 KB |
Output is correct |
30 |
Correct |
31 ms |
8696 KB |
Output is correct |
31 |
Correct |
30 ms |
8648 KB |
Output is correct |
32 |
Correct |
29 ms |
8668 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
3 ms |
1272 KB |
Output is correct |
36 |
Correct |
3 ms |
1148 KB |
Output is correct |
37 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
2 ms |
1020 KB |
Output is correct |
8 |
Correct |
2 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 |
1 ms |
1272 KB |
Output is correct |
12 |
Correct |
3 ms |
1272 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
9 ms |
3320 KB |
Output is correct |
18 |
Correct |
9 ms |
3320 KB |
Output is correct |
19 |
Correct |
9 ms |
3320 KB |
Output is correct |
20 |
Correct |
6 ms |
2936 KB |
Output is correct |
21 |
Correct |
7 ms |
3064 KB |
Output is correct |
22 |
Correct |
7 ms |
3064 KB |
Output is correct |
23 |
Correct |
7 ms |
3064 KB |
Output is correct |
24 |
Correct |
5 ms |
2424 KB |
Output is correct |
25 |
Correct |
54 ms |
10332 KB |
Output is correct |
26 |
Correct |
54 ms |
10332 KB |
Output is correct |
27 |
Correct |
55 ms |
10360 KB |
Output is correct |
28 |
Correct |
22 ms |
8056 KB |
Output is correct |
29 |
Correct |
30 ms |
8696 KB |
Output is correct |
30 |
Correct |
31 ms |
8696 KB |
Output is correct |
31 |
Correct |
30 ms |
8648 KB |
Output is correct |
32 |
Correct |
29 ms |
8668 KB |
Output is correct |
33 |
Correct |
159 ms |
44920 KB |
Output is correct |
34 |
Correct |
158 ms |
44896 KB |
Output is correct |
35 |
Correct |
166 ms |
44768 KB |
Output is correct |
36 |
Correct |
167 ms |
44792 KB |
Output is correct |
37 |
Correct |
900 ms |
75428 KB |
Output is correct |
38 |
Correct |
887 ms |
75272 KB |
Output is correct |
39 |
Correct |
883 ms |
75408 KB |
Output is correct |
40 |
Correct |
809 ms |
71204 KB |
Output is correct |
41 |
Correct |
246 ms |
46144 KB |
Output is correct |
42 |
Correct |
294 ms |
47728 KB |
Output is correct |
43 |
Correct |
394 ms |
55120 KB |
Output is correct |
44 |
Correct |
408 ms |
55292 KB |
Output is correct |
45 |
Correct |
200 ms |
34940 KB |
Output is correct |
46 |
Correct |
191 ms |
30536 KB |
Output is correct |
47 |
Correct |
389 ms |
55320 KB |
Output is correct |
48 |
Correct |
395 ms |
55276 KB |
Output is correct |
49 |
Correct |
2 ms |
376 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
3 ms |
1272 KB |
Output is correct |
52 |
Correct |
3 ms |
1148 KB |
Output is correct |
53 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
20984 KB |
Output is correct |
2 |
Correct |
18 ms |
18040 KB |
Output is correct |
3 |
Correct |
18 ms |
20932 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
19 ms |
20984 KB |
Output is correct |
6 |
Correct |
19 ms |
20856 KB |
Output is correct |
7 |
Correct |
19 ms |
20856 KB |
Output is correct |
8 |
Correct |
19 ms |
20984 KB |
Output is correct |
9 |
Correct |
19 ms |
20856 KB |
Output is correct |
10 |
Correct |
18 ms |
20600 KB |
Output is correct |
11 |
Correct |
19 ms |
20728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
1672 ms |
194768 KB |
Output is correct |
3 |
Correct |
3854 ms |
382120 KB |
Output is correct |
4 |
Correct |
3818 ms |
383656 KB |
Output is correct |
5 |
Correct |
3858 ms |
383712 KB |
Output is correct |
6 |
Correct |
800 ms |
193472 KB |
Output is correct |
7 |
Correct |
1671 ms |
358732 KB |
Output is correct |
8 |
Correct |
1758 ms |
367936 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
1272 KB |
Output is correct |
12 |
Correct |
3 ms |
1148 KB |
Output is correct |
13 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
2 ms |
1020 KB |
Output is correct |
8 |
Correct |
2 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 |
1 ms |
1272 KB |
Output is correct |
12 |
Correct |
3 ms |
1272 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
9 ms |
3320 KB |
Output is correct |
18 |
Correct |
9 ms |
3320 KB |
Output is correct |
19 |
Correct |
9 ms |
3320 KB |
Output is correct |
20 |
Correct |
6 ms |
2936 KB |
Output is correct |
21 |
Correct |
7 ms |
3064 KB |
Output is correct |
22 |
Correct |
7 ms |
3064 KB |
Output is correct |
23 |
Correct |
7 ms |
3064 KB |
Output is correct |
24 |
Correct |
5 ms |
2424 KB |
Output is correct |
25 |
Correct |
54 ms |
10332 KB |
Output is correct |
26 |
Correct |
54 ms |
10332 KB |
Output is correct |
27 |
Correct |
55 ms |
10360 KB |
Output is correct |
28 |
Correct |
22 ms |
8056 KB |
Output is correct |
29 |
Correct |
30 ms |
8696 KB |
Output is correct |
30 |
Correct |
31 ms |
8696 KB |
Output is correct |
31 |
Correct |
30 ms |
8648 KB |
Output is correct |
32 |
Correct |
29 ms |
8668 KB |
Output is correct |
33 |
Correct |
159 ms |
44920 KB |
Output is correct |
34 |
Correct |
158 ms |
44896 KB |
Output is correct |
35 |
Correct |
166 ms |
44768 KB |
Output is correct |
36 |
Correct |
167 ms |
44792 KB |
Output is correct |
37 |
Correct |
900 ms |
75428 KB |
Output is correct |
38 |
Correct |
887 ms |
75272 KB |
Output is correct |
39 |
Correct |
883 ms |
75408 KB |
Output is correct |
40 |
Correct |
809 ms |
71204 KB |
Output is correct |
41 |
Correct |
246 ms |
46144 KB |
Output is correct |
42 |
Correct |
294 ms |
47728 KB |
Output is correct |
43 |
Correct |
394 ms |
55120 KB |
Output is correct |
44 |
Correct |
408 ms |
55292 KB |
Output is correct |
45 |
Correct |
200 ms |
34940 KB |
Output is correct |
46 |
Correct |
191 ms |
30536 KB |
Output is correct |
47 |
Correct |
389 ms |
55320 KB |
Output is correct |
48 |
Correct |
395 ms |
55276 KB |
Output is correct |
49 |
Correct |
20 ms |
20984 KB |
Output is correct |
50 |
Correct |
18 ms |
18040 KB |
Output is correct |
51 |
Correct |
18 ms |
20932 KB |
Output is correct |
52 |
Correct |
2 ms |
376 KB |
Output is correct |
53 |
Correct |
19 ms |
20984 KB |
Output is correct |
54 |
Correct |
19 ms |
20856 KB |
Output is correct |
55 |
Correct |
19 ms |
20856 KB |
Output is correct |
56 |
Correct |
19 ms |
20984 KB |
Output is correct |
57 |
Correct |
19 ms |
20856 KB |
Output is correct |
58 |
Correct |
18 ms |
20600 KB |
Output is correct |
59 |
Correct |
19 ms |
20728 KB |
Output is correct |
60 |
Correct |
2 ms |
632 KB |
Output is correct |
61 |
Correct |
1672 ms |
194768 KB |
Output is correct |
62 |
Correct |
3854 ms |
382120 KB |
Output is correct |
63 |
Correct |
3818 ms |
383656 KB |
Output is correct |
64 |
Correct |
3858 ms |
383712 KB |
Output is correct |
65 |
Correct |
800 ms |
193472 KB |
Output is correct |
66 |
Correct |
1671 ms |
358732 KB |
Output is correct |
67 |
Correct |
1758 ms |
367936 KB |
Output is correct |
68 |
Correct |
2346 ms |
368008 KB |
Output is correct |
69 |
Correct |
2303 ms |
367944 KB |
Output is correct |
70 |
Correct |
2423 ms |
367972 KB |
Output is correct |
71 |
Correct |
2480 ms |
368032 KB |
Output is correct |
72 |
Execution timed out |
5100 ms |
465160 KB |
Time limit exceeded |
73 |
Halted |
0 ms |
0 KB |
- |