# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
285452 |
2020-08-29T03:31:09 Z |
caoash |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
832228 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
const int mxN=2.5e3;
int n, m, l[mxN], r[mxN], ft[mxN+1];
vector<ar<int, 2>> p[mxN][mxN][2];
void upd(int i, int x) {
for(++i; i<=m; i+=i&-i)
ft[i]+=x;
}
int qry(int i) {
int r=0;
for(; i; i-=i&-i)
r+=ft[i];
return r;
}
void gr(vector<vector<int>> &a, int b) {
int n=a.size(), m=a[0].size();
vector<ar<int, 3>> s;
for(int i=0; i<n; ++i) {
for(int j=0; j<m; ++j) {
l[j]=j-1;
while(~l[j]&&a[i][l[j]]<=a[i][j])
l[j]=l[l[j]];
}
for(int j=m-1; ~j; --j) {
r[j]=j+1;
while(r[j]<m&&a[i][r[j]]<=a[i][j])
r[j]=r[r[j]];
if(~l[j]&&r[j]<m)
s.push_back({l[j]+1, r[j]-1, i});
}
}
sort(s.begin(), s.end());
for(int i=0, j; i<s.size(); i=j+1) {
for(j=i; j+1<s.size()&&s[j+1][0]==s[i][0]&&s[j+1][1]==s[i][1]&&s[j+1][2]<=s[j][2]+1; ++j);
int l1=s[i][0], r1=s[i][1], l2=s[i][2], r2=s[j][2], x2=r2, y2=r1;
if(b)
swap(x2, y2);
for(int k=l2; k<=r2; ++k) {
int x=k, y=l1;
if(b)
swap(x, y);
p[x][y][b].push_back({-x2, y2});
}
}
}
long long count_rectangles(vector<vector<int>> a) {
n=a.size();
m=a[0].size();
vector<vector<int>> b(m, vector<int>(n));
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
b[j][i]=a[i][j];
gr(a, 0);
gr(b, 1);
int ans=0;
for(int i=1; i<n-1; ++i) {
for(int j=1; j<m-1; ++j) {
for(int k : {0, 1})
sort(p[i][j][k].begin(), p[i][j][k].end());
int d=0;
for(int c=0; c<p[i][j][1].size(); ++c) {
while(d<p[i][j][0].size()&&p[i][j][0][d]<=p[i][j][1][c])
upd(p[i][j][0][d++][1], 1);
ans+=qry(p[i][j][1][c][1]+1);
}
while(d)
upd(p[i][j][0][--d][1], -1);
}
}
return ans;
}
Compilation message
rect.cpp: In function 'void gr(std::vector<std::vector<int> >&, int)':
rect.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i=0, j; i<s.size(); i=j+1) {
| ~^~~~~~~~~
rect.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(j=i; j+1<s.size()&&s[j+1][0]==s[i][0]&&s[j+1][1]==s[i][1]&&s[j+1][2]<=s[j][2]+1; ++j);
| ~~~^~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int c=0; c<p[i][j][1].size(); ++c) {
| ~^~~~~~~~~~~~~~~~~~
rect.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | while(d<p[i][j][0].size()&&p[i][j][0][d]<=p[i][j][1][c])
| ~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
293880 KB |
Output is correct |
2 |
Correct |
198 ms |
294008 KB |
Output is correct |
3 |
Correct |
197 ms |
294008 KB |
Output is correct |
4 |
Correct |
198 ms |
293880 KB |
Output is correct |
5 |
Correct |
203 ms |
293880 KB |
Output is correct |
6 |
Correct |
196 ms |
294008 KB |
Output is correct |
7 |
Correct |
199 ms |
293880 KB |
Output is correct |
8 |
Correct |
199 ms |
293832 KB |
Output is correct |
9 |
Correct |
199 ms |
293884 KB |
Output is correct |
10 |
Correct |
201 ms |
293880 KB |
Output is correct |
11 |
Correct |
196 ms |
293880 KB |
Output is correct |
12 |
Correct |
201 ms |
293880 KB |
Output is correct |
13 |
Correct |
203 ms |
293880 KB |
Output is correct |
14 |
Correct |
212 ms |
293880 KB |
Output is correct |
15 |
Correct |
206 ms |
293880 KB |
Output is correct |
16 |
Correct |
197 ms |
293880 KB |
Output is correct |
17 |
Correct |
199 ms |
294008 KB |
Output is correct |
18 |
Correct |
197 ms |
294008 KB |
Output is correct |
19 |
Correct |
198 ms |
293880 KB |
Output is correct |
20 |
Correct |
197 ms |
294008 KB |
Output is correct |
21 |
Correct |
199 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
293880 KB |
Output is correct |
2 |
Correct |
198 ms |
294008 KB |
Output is correct |
3 |
Correct |
197 ms |
294008 KB |
Output is correct |
4 |
Correct |
198 ms |
293880 KB |
Output is correct |
5 |
Correct |
203 ms |
293880 KB |
Output is correct |
6 |
Correct |
196 ms |
294008 KB |
Output is correct |
7 |
Correct |
199 ms |
293880 KB |
Output is correct |
8 |
Correct |
199 ms |
293832 KB |
Output is correct |
9 |
Correct |
199 ms |
293884 KB |
Output is correct |
10 |
Correct |
201 ms |
293880 KB |
Output is correct |
11 |
Correct |
196 ms |
293880 KB |
Output is correct |
12 |
Correct |
201 ms |
293880 KB |
Output is correct |
13 |
Correct |
203 ms |
293880 KB |
Output is correct |
14 |
Correct |
212 ms |
293880 KB |
Output is correct |
15 |
Correct |
206 ms |
293880 KB |
Output is correct |
16 |
Correct |
197 ms |
293880 KB |
Output is correct |
17 |
Correct |
200 ms |
294392 KB |
Output is correct |
18 |
Correct |
200 ms |
294392 KB |
Output is correct |
19 |
Correct |
200 ms |
294480 KB |
Output is correct |
20 |
Correct |
199 ms |
294264 KB |
Output is correct |
21 |
Correct |
200 ms |
294264 KB |
Output is correct |
22 |
Correct |
202 ms |
294264 KB |
Output is correct |
23 |
Correct |
203 ms |
294264 KB |
Output is correct |
24 |
Correct |
200 ms |
294136 KB |
Output is correct |
25 |
Correct |
199 ms |
294008 KB |
Output is correct |
26 |
Correct |
197 ms |
294008 KB |
Output is correct |
27 |
Correct |
198 ms |
293880 KB |
Output is correct |
28 |
Correct |
197 ms |
294008 KB |
Output is correct |
29 |
Correct |
199 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
293880 KB |
Output is correct |
2 |
Correct |
198 ms |
294008 KB |
Output is correct |
3 |
Correct |
197 ms |
294008 KB |
Output is correct |
4 |
Correct |
198 ms |
293880 KB |
Output is correct |
5 |
Correct |
203 ms |
293880 KB |
Output is correct |
6 |
Correct |
196 ms |
294008 KB |
Output is correct |
7 |
Correct |
199 ms |
293880 KB |
Output is correct |
8 |
Correct |
199 ms |
293832 KB |
Output is correct |
9 |
Correct |
199 ms |
293884 KB |
Output is correct |
10 |
Correct |
201 ms |
293880 KB |
Output is correct |
11 |
Correct |
196 ms |
293880 KB |
Output is correct |
12 |
Correct |
201 ms |
293880 KB |
Output is correct |
13 |
Correct |
203 ms |
293880 KB |
Output is correct |
14 |
Correct |
212 ms |
293880 KB |
Output is correct |
15 |
Correct |
206 ms |
293880 KB |
Output is correct |
16 |
Correct |
197 ms |
293880 KB |
Output is correct |
17 |
Correct |
200 ms |
294392 KB |
Output is correct |
18 |
Correct |
200 ms |
294392 KB |
Output is correct |
19 |
Correct |
200 ms |
294480 KB |
Output is correct |
20 |
Correct |
199 ms |
294264 KB |
Output is correct |
21 |
Correct |
200 ms |
294264 KB |
Output is correct |
22 |
Correct |
202 ms |
294264 KB |
Output is correct |
23 |
Correct |
203 ms |
294264 KB |
Output is correct |
24 |
Correct |
200 ms |
294136 KB |
Output is correct |
25 |
Correct |
222 ms |
297500 KB |
Output is correct |
26 |
Correct |
218 ms |
297500 KB |
Output is correct |
27 |
Correct |
225 ms |
297628 KB |
Output is correct |
28 |
Correct |
214 ms |
295616 KB |
Output is correct |
29 |
Correct |
226 ms |
296516 KB |
Output is correct |
30 |
Correct |
225 ms |
296628 KB |
Output is correct |
31 |
Correct |
223 ms |
296500 KB |
Output is correct |
32 |
Correct |
221 ms |
296516 KB |
Output is correct |
33 |
Correct |
199 ms |
294008 KB |
Output is correct |
34 |
Correct |
197 ms |
294008 KB |
Output is correct |
35 |
Correct |
198 ms |
293880 KB |
Output is correct |
36 |
Correct |
197 ms |
294008 KB |
Output is correct |
37 |
Correct |
199 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
293880 KB |
Output is correct |
2 |
Correct |
198 ms |
294008 KB |
Output is correct |
3 |
Correct |
197 ms |
294008 KB |
Output is correct |
4 |
Correct |
198 ms |
293880 KB |
Output is correct |
5 |
Correct |
203 ms |
293880 KB |
Output is correct |
6 |
Correct |
196 ms |
294008 KB |
Output is correct |
7 |
Correct |
199 ms |
293880 KB |
Output is correct |
8 |
Correct |
199 ms |
293832 KB |
Output is correct |
9 |
Correct |
199 ms |
293884 KB |
Output is correct |
10 |
Correct |
201 ms |
293880 KB |
Output is correct |
11 |
Correct |
196 ms |
293880 KB |
Output is correct |
12 |
Correct |
201 ms |
293880 KB |
Output is correct |
13 |
Correct |
203 ms |
293880 KB |
Output is correct |
14 |
Correct |
212 ms |
293880 KB |
Output is correct |
15 |
Correct |
206 ms |
293880 KB |
Output is correct |
16 |
Correct |
197 ms |
293880 KB |
Output is correct |
17 |
Correct |
200 ms |
294392 KB |
Output is correct |
18 |
Correct |
200 ms |
294392 KB |
Output is correct |
19 |
Correct |
200 ms |
294480 KB |
Output is correct |
20 |
Correct |
199 ms |
294264 KB |
Output is correct |
21 |
Correct |
200 ms |
294264 KB |
Output is correct |
22 |
Correct |
202 ms |
294264 KB |
Output is correct |
23 |
Correct |
203 ms |
294264 KB |
Output is correct |
24 |
Correct |
200 ms |
294136 KB |
Output is correct |
25 |
Correct |
222 ms |
297500 KB |
Output is correct |
26 |
Correct |
218 ms |
297500 KB |
Output is correct |
27 |
Correct |
225 ms |
297628 KB |
Output is correct |
28 |
Correct |
214 ms |
295616 KB |
Output is correct |
29 |
Correct |
226 ms |
296516 KB |
Output is correct |
30 |
Correct |
225 ms |
296628 KB |
Output is correct |
31 |
Correct |
223 ms |
296500 KB |
Output is correct |
32 |
Correct |
221 ms |
296516 KB |
Output is correct |
33 |
Correct |
343 ms |
320936 KB |
Output is correct |
34 |
Correct |
319 ms |
316200 KB |
Output is correct |
35 |
Correct |
315 ms |
316476 KB |
Output is correct |
36 |
Correct |
304 ms |
311644 KB |
Output is correct |
37 |
Correct |
493 ms |
339312 KB |
Output is correct |
38 |
Correct |
494 ms |
339180 KB |
Output is correct |
39 |
Correct |
493 ms |
339684 KB |
Output is correct |
40 |
Correct |
468 ms |
336724 KB |
Output is correct |
41 |
Correct |
358 ms |
311212 KB |
Output is correct |
42 |
Correct |
412 ms |
315876 KB |
Output is correct |
43 |
Correct |
563 ms |
325068 KB |
Output is correct |
44 |
Correct |
557 ms |
327184 KB |
Output is correct |
45 |
Correct |
370 ms |
310660 KB |
Output is correct |
46 |
Correct |
373 ms |
310480 KB |
Output is correct |
47 |
Correct |
537 ms |
324740 KB |
Output is correct |
48 |
Correct |
549 ms |
325640 KB |
Output is correct |
49 |
Correct |
199 ms |
294008 KB |
Output is correct |
50 |
Correct |
197 ms |
294008 KB |
Output is correct |
51 |
Correct |
198 ms |
293880 KB |
Output is correct |
52 |
Correct |
197 ms |
294008 KB |
Output is correct |
53 |
Correct |
199 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
199 ms |
294524 KB |
Output is correct |
2 |
Correct |
198 ms |
294392 KB |
Output is correct |
3 |
Correct |
199 ms |
294136 KB |
Output is correct |
4 |
Correct |
196 ms |
293880 KB |
Output is correct |
5 |
Correct |
207 ms |
294392 KB |
Output is correct |
6 |
Correct |
199 ms |
294392 KB |
Output is correct |
7 |
Correct |
210 ms |
294484 KB |
Output is correct |
8 |
Correct |
198 ms |
294264 KB |
Output is correct |
9 |
Correct |
198 ms |
294392 KB |
Output is correct |
10 |
Correct |
205 ms |
294136 KB |
Output is correct |
11 |
Correct |
199 ms |
294392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
199 ms |
293880 KB |
Output is correct |
2 |
Correct |
1239 ms |
394888 KB |
Output is correct |
3 |
Correct |
2535 ms |
502016 KB |
Output is correct |
4 |
Correct |
2564 ms |
502988 KB |
Output is correct |
5 |
Correct |
2591 ms |
502992 KB |
Output is correct |
6 |
Correct |
334 ms |
332100 KB |
Output is correct |
7 |
Correct |
461 ms |
364092 KB |
Output is correct |
8 |
Correct |
465 ms |
368632 KB |
Output is correct |
9 |
Correct |
199 ms |
294008 KB |
Output is correct |
10 |
Correct |
197 ms |
294008 KB |
Output is correct |
11 |
Correct |
198 ms |
293880 KB |
Output is correct |
12 |
Correct |
197 ms |
294008 KB |
Output is correct |
13 |
Correct |
199 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
293880 KB |
Output is correct |
2 |
Correct |
198 ms |
294008 KB |
Output is correct |
3 |
Correct |
197 ms |
294008 KB |
Output is correct |
4 |
Correct |
198 ms |
293880 KB |
Output is correct |
5 |
Correct |
203 ms |
293880 KB |
Output is correct |
6 |
Correct |
196 ms |
294008 KB |
Output is correct |
7 |
Correct |
199 ms |
293880 KB |
Output is correct |
8 |
Correct |
199 ms |
293832 KB |
Output is correct |
9 |
Correct |
199 ms |
293884 KB |
Output is correct |
10 |
Correct |
201 ms |
293880 KB |
Output is correct |
11 |
Correct |
196 ms |
293880 KB |
Output is correct |
12 |
Correct |
201 ms |
293880 KB |
Output is correct |
13 |
Correct |
203 ms |
293880 KB |
Output is correct |
14 |
Correct |
212 ms |
293880 KB |
Output is correct |
15 |
Correct |
206 ms |
293880 KB |
Output is correct |
16 |
Correct |
197 ms |
293880 KB |
Output is correct |
17 |
Correct |
200 ms |
294392 KB |
Output is correct |
18 |
Correct |
200 ms |
294392 KB |
Output is correct |
19 |
Correct |
200 ms |
294480 KB |
Output is correct |
20 |
Correct |
199 ms |
294264 KB |
Output is correct |
21 |
Correct |
200 ms |
294264 KB |
Output is correct |
22 |
Correct |
202 ms |
294264 KB |
Output is correct |
23 |
Correct |
203 ms |
294264 KB |
Output is correct |
24 |
Correct |
200 ms |
294136 KB |
Output is correct |
25 |
Correct |
222 ms |
297500 KB |
Output is correct |
26 |
Correct |
218 ms |
297500 KB |
Output is correct |
27 |
Correct |
225 ms |
297628 KB |
Output is correct |
28 |
Correct |
214 ms |
295616 KB |
Output is correct |
29 |
Correct |
226 ms |
296516 KB |
Output is correct |
30 |
Correct |
225 ms |
296628 KB |
Output is correct |
31 |
Correct |
223 ms |
296500 KB |
Output is correct |
32 |
Correct |
221 ms |
296516 KB |
Output is correct |
33 |
Correct |
343 ms |
320936 KB |
Output is correct |
34 |
Correct |
319 ms |
316200 KB |
Output is correct |
35 |
Correct |
315 ms |
316476 KB |
Output is correct |
36 |
Correct |
304 ms |
311644 KB |
Output is correct |
37 |
Correct |
493 ms |
339312 KB |
Output is correct |
38 |
Correct |
494 ms |
339180 KB |
Output is correct |
39 |
Correct |
493 ms |
339684 KB |
Output is correct |
40 |
Correct |
468 ms |
336724 KB |
Output is correct |
41 |
Correct |
358 ms |
311212 KB |
Output is correct |
42 |
Correct |
412 ms |
315876 KB |
Output is correct |
43 |
Correct |
563 ms |
325068 KB |
Output is correct |
44 |
Correct |
557 ms |
327184 KB |
Output is correct |
45 |
Correct |
370 ms |
310660 KB |
Output is correct |
46 |
Correct |
373 ms |
310480 KB |
Output is correct |
47 |
Correct |
537 ms |
324740 KB |
Output is correct |
48 |
Correct |
549 ms |
325640 KB |
Output is correct |
49 |
Correct |
199 ms |
294524 KB |
Output is correct |
50 |
Correct |
198 ms |
294392 KB |
Output is correct |
51 |
Correct |
199 ms |
294136 KB |
Output is correct |
52 |
Correct |
196 ms |
293880 KB |
Output is correct |
53 |
Correct |
207 ms |
294392 KB |
Output is correct |
54 |
Correct |
199 ms |
294392 KB |
Output is correct |
55 |
Correct |
210 ms |
294484 KB |
Output is correct |
56 |
Correct |
198 ms |
294264 KB |
Output is correct |
57 |
Correct |
198 ms |
294392 KB |
Output is correct |
58 |
Correct |
205 ms |
294136 KB |
Output is correct |
59 |
Correct |
199 ms |
294392 KB |
Output is correct |
60 |
Correct |
199 ms |
293880 KB |
Output is correct |
61 |
Correct |
1239 ms |
394888 KB |
Output is correct |
62 |
Correct |
2535 ms |
502016 KB |
Output is correct |
63 |
Correct |
2564 ms |
502988 KB |
Output is correct |
64 |
Correct |
2591 ms |
502992 KB |
Output is correct |
65 |
Correct |
334 ms |
332100 KB |
Output is correct |
66 |
Correct |
461 ms |
364092 KB |
Output is correct |
67 |
Correct |
465 ms |
368632 KB |
Output is correct |
68 |
Correct |
2508 ms |
601804 KB |
Output is correct |
69 |
Correct |
1792 ms |
535080 KB |
Output is correct |
70 |
Correct |
2123 ms |
541376 KB |
Output is correct |
71 |
Correct |
1863 ms |
474588 KB |
Output is correct |
72 |
Execution timed out |
5127 ms |
832228 KB |
Time limit exceeded |
73 |
Halted |
0 ms |
0 KB |
- |