# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
156316 |
2019-10-05T02:44:42 Z |
wilwxk |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
499440 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];
vector<tuple<int, int, int, int> > ve;
int n, m, respf;
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++) ve.push_back({qv[ii][jj][1], qv[ii][jj][2], qv[ii][jj][3], qv[ii][jj][0]});
sort(ve.begin(), ve.end());
auto it=unique(ve.begin(), ve.end());
ve.resize(it-ve.begin());
for(auto cur : ve) {
// printf("%d %d\n", ii, jj);
short a, b, c, d; tie(a, b, c, d)=cur;
if(checa(a, b, c, d)) respf++;
}
return respf;
}
# |
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 |
2 ms |
888 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 |
3 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 |
636 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 |
1144 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 |
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 |
2 ms |
888 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 |
3 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 |
636 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
3064 KB |
Output is correct |
18 |
Correct |
8 ms |
3064 KB |
Output is correct |
19 |
Correct |
7 ms |
3064 KB |
Output is correct |
20 |
Correct |
6 ms |
3192 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 |
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 |
3 ms |
1272 KB |
Output is correct |
28 |
Correct |
3 ms |
1144 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 |
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 |
2 ms |
888 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 |
3 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 |
636 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
3064 KB |
Output is correct |
18 |
Correct |
8 ms |
3064 KB |
Output is correct |
19 |
Correct |
7 ms |
3064 KB |
Output is correct |
20 |
Correct |
6 ms |
3192 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 |
2552 KB |
Output is correct |
25 |
Correct |
36 ms |
9076 KB |
Output is correct |
26 |
Correct |
39 ms |
9036 KB |
Output is correct |
27 |
Correct |
37 ms |
8948 KB |
Output is correct |
28 |
Correct |
27 ms |
9076 KB |
Output is correct |
29 |
Correct |
30 ms |
8948 KB |
Output is correct |
30 |
Correct |
30 ms |
9076 KB |
Output is correct |
31 |
Correct |
29 ms |
9080 KB |
Output is correct |
32 |
Correct |
29 ms |
8944 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 |
1144 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 |
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 |
2 ms |
888 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 |
3 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 |
636 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
3064 KB |
Output is correct |
18 |
Correct |
8 ms |
3064 KB |
Output is correct |
19 |
Correct |
7 ms |
3064 KB |
Output is correct |
20 |
Correct |
6 ms |
3192 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 |
2552 KB |
Output is correct |
25 |
Correct |
36 ms |
9076 KB |
Output is correct |
26 |
Correct |
39 ms |
9036 KB |
Output is correct |
27 |
Correct |
37 ms |
8948 KB |
Output is correct |
28 |
Correct |
27 ms |
9076 KB |
Output is correct |
29 |
Correct |
30 ms |
8948 KB |
Output is correct |
30 |
Correct |
30 ms |
9076 KB |
Output is correct |
31 |
Correct |
29 ms |
9080 KB |
Output is correct |
32 |
Correct |
29 ms |
8944 KB |
Output is correct |
33 |
Correct |
212 ms |
53084 KB |
Output is correct |
34 |
Correct |
199 ms |
53340 KB |
Output is correct |
35 |
Correct |
223 ms |
53236 KB |
Output is correct |
36 |
Correct |
216 ms |
53212 KB |
Output is correct |
37 |
Correct |
523 ms |
53128 KB |
Output is correct |
38 |
Correct |
524 ms |
53184 KB |
Output is correct |
39 |
Correct |
528 ms |
53184 KB |
Output is correct |
40 |
Correct |
495 ms |
51044 KB |
Output is correct |
41 |
Correct |
247 ms |
53336 KB |
Output is correct |
42 |
Correct |
306 ms |
53084 KB |
Output is correct |
43 |
Correct |
382 ms |
53284 KB |
Output is correct |
44 |
Correct |
369 ms |
53180 KB |
Output is correct |
45 |
Correct |
180 ms |
33896 KB |
Output is correct |
46 |
Correct |
176 ms |
29648 KB |
Output is correct |
47 |
Correct |
350 ms |
53164 KB |
Output is correct |
48 |
Correct |
344 ms |
53212 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 |
1144 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 |
17 ms |
17912 KB |
Output is correct |
3 |
Correct |
19 ms |
20984 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
19 ms |
20988 KB |
Output is correct |
6 |
Correct |
20 ms |
20984 KB |
Output is correct |
7 |
Correct |
19 ms |
20988 KB |
Output is correct |
8 |
Correct |
19 ms |
20984 KB |
Output is correct |
9 |
Correct |
20 ms |
20984 KB |
Output is correct |
10 |
Correct |
21 ms |
20600 KB |
Output is correct |
11 |
Correct |
21 ms |
20728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
1534 ms |
253428 KB |
Output is correct |
3 |
Correct |
3504 ms |
497988 KB |
Output is correct |
4 |
Correct |
3508 ms |
499360 KB |
Output is correct |
5 |
Correct |
3548 ms |
499412 KB |
Output is correct |
6 |
Correct |
1089 ms |
259208 KB |
Output is correct |
7 |
Correct |
2197 ms |
490216 KB |
Output is correct |
8 |
Correct |
2365 ms |
499356 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 |
1144 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 |
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 |
2 ms |
888 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 |
3 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 |
636 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
3064 KB |
Output is correct |
18 |
Correct |
8 ms |
3064 KB |
Output is correct |
19 |
Correct |
7 ms |
3064 KB |
Output is correct |
20 |
Correct |
6 ms |
3192 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 |
2552 KB |
Output is correct |
25 |
Correct |
36 ms |
9076 KB |
Output is correct |
26 |
Correct |
39 ms |
9036 KB |
Output is correct |
27 |
Correct |
37 ms |
8948 KB |
Output is correct |
28 |
Correct |
27 ms |
9076 KB |
Output is correct |
29 |
Correct |
30 ms |
8948 KB |
Output is correct |
30 |
Correct |
30 ms |
9076 KB |
Output is correct |
31 |
Correct |
29 ms |
9080 KB |
Output is correct |
32 |
Correct |
29 ms |
8944 KB |
Output is correct |
33 |
Correct |
212 ms |
53084 KB |
Output is correct |
34 |
Correct |
199 ms |
53340 KB |
Output is correct |
35 |
Correct |
223 ms |
53236 KB |
Output is correct |
36 |
Correct |
216 ms |
53212 KB |
Output is correct |
37 |
Correct |
523 ms |
53128 KB |
Output is correct |
38 |
Correct |
524 ms |
53184 KB |
Output is correct |
39 |
Correct |
528 ms |
53184 KB |
Output is correct |
40 |
Correct |
495 ms |
51044 KB |
Output is correct |
41 |
Correct |
247 ms |
53336 KB |
Output is correct |
42 |
Correct |
306 ms |
53084 KB |
Output is correct |
43 |
Correct |
382 ms |
53284 KB |
Output is correct |
44 |
Correct |
369 ms |
53180 KB |
Output is correct |
45 |
Correct |
180 ms |
33896 KB |
Output is correct |
46 |
Correct |
176 ms |
29648 KB |
Output is correct |
47 |
Correct |
350 ms |
53164 KB |
Output is correct |
48 |
Correct |
344 ms |
53212 KB |
Output is correct |
49 |
Correct |
20 ms |
20984 KB |
Output is correct |
50 |
Correct |
17 ms |
17912 KB |
Output is correct |
51 |
Correct |
19 ms |
20984 KB |
Output is correct |
52 |
Correct |
2 ms |
376 KB |
Output is correct |
53 |
Correct |
19 ms |
20988 KB |
Output is correct |
54 |
Correct |
20 ms |
20984 KB |
Output is correct |
55 |
Correct |
19 ms |
20988 KB |
Output is correct |
56 |
Correct |
19 ms |
20984 KB |
Output is correct |
57 |
Correct |
20 ms |
20984 KB |
Output is correct |
58 |
Correct |
21 ms |
20600 KB |
Output is correct |
59 |
Correct |
21 ms |
20728 KB |
Output is correct |
60 |
Correct |
2 ms |
632 KB |
Output is correct |
61 |
Correct |
1534 ms |
253428 KB |
Output is correct |
62 |
Correct |
3504 ms |
497988 KB |
Output is correct |
63 |
Correct |
3508 ms |
499360 KB |
Output is correct |
64 |
Correct |
3548 ms |
499412 KB |
Output is correct |
65 |
Correct |
1089 ms |
259208 KB |
Output is correct |
66 |
Correct |
2197 ms |
490216 KB |
Output is correct |
67 |
Correct |
2365 ms |
499356 KB |
Output is correct |
68 |
Correct |
3316 ms |
499344 KB |
Output is correct |
69 |
Correct |
3058 ms |
499284 KB |
Output is correct |
70 |
Correct |
3207 ms |
499300 KB |
Output is correct |
71 |
Correct |
3195 ms |
499420 KB |
Output is correct |
72 |
Execution timed out |
5114 ms |
499440 KB |
Time limit exceeded |
73 |
Halted |
0 ms |
0 KB |
- |