# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
535963 |
2022-03-12T01:37:28 Z |
jamezzz |
Rectangles (IOI19_rect) |
C++17 |
|
2406 ms |
737872 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define INF 1023456789
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;
#define maxn 2505
int n,m,ft[maxn+5];
vector<ii> h[maxn][maxn],v[maxn][maxn];
void up(int x,int v){
++x;
while(x<=maxn)ft[x]+=v,x+=x&-x;
}
int qry(int x,int y){
++y;int res=0;
while(y)res+=ft[y],y-=y&-y;
while(x)res-=ft[x],x-=x&-x;
return res;
}
ll count_rectangles(vector<vector<int>> a){
n=sz(a);m=sz(a[0]);
if(min(n,m)<=2)return 0;
for(int i=0;i<n;++i){
vector<ii> s;
s.pb({INF,-1});
for(int j=0;j<m;++j){
while(s.back().fi<a[i][j]){
if(j-s.back().se>1)h[i][s.back().se+1].pb({j-1,i});
while(sz(s)>=2&&s[sz(s)-1].fi==s[sz(s)-2].fi)s.pop_back();
s.pop_back();
}
if(j-s.back().se>1)h[i][s.back().se+1].pb({j-1,i});
s.pb({a[i][j],j});
}
}
for(int j=0;j<m;++j){
vector<ii> s;
s.pb({INF,-1});
for(int i=0;i<n;++i){
while(s.back().fi<a[i][j]){
if(i-s.back().se>1)v[s.back().se+1][j].pb({i-1,j});
while(sz(s)>=2&&s[sz(s)-1].fi==s[sz(s)-2].fi)s.pop_back();
s.pop_back();
}
if(i-s.back().se>1)v[s.back().se+1][j].pb({i-1,j});
s.pb({a[i][j],i});
}
}
for(int i=n-2;i>0;--i){
for(int j=m-2;j>0;--j){
for(ii &p:h[i][j]){
auto it=lower_bound(all(h[i+1][j]),p);
if(it!=h[i+1][j].end()&&(*it).fi==p.fi){
p.se=(*it).se;
}
}
for(ii &p:v[i][j]){
auto it=lower_bound(all(v[i][j+1]),p);
if(it!=v[i][j+1].end()&&(*it).fi==p.fi){
p.se=(*it).se;
}
}
}
}
for(int i=0;i<n;++i)for(int j=0;j<m;++j)for(ii &p:h[i][j])swap(p.fi,p.se);
ll ans=0;
for(int i=1;i<n-1;++i){
for(int j=1;j<m-1;++j){
//pf("h[%d][%d]:\n",i,j);
//for(ii pr:h[i][j])pf("%d %d %d %d\n",i,j,pr.fi,pr.se);
//pf("v[%d][%d]:\n",i,j);
//for(ii pr:v[i][j])pf("%d %d %d %d\n",i,j,pr.fi,pr.se);
sort(all(h[i][j]),[](ii &a,ii &b){return a.se<b.se;});
sort(all(v[i][j]),[](ii &a,ii &b){return a.se<b.se;});
int curh=0,curv=0,mxh=sz(h[i][j]),mxv=sz(v[i][j]);
while(curv!=mxv){
while(curh!=mxh&&h[i][j][curh].se<=v[i][j][curv].se){
up(h[i][j][curh++].fi,1);
}
ans+=qry(v[i][j][curv++].fi,maxn-1);
}
for(int k=0;k<curh;++k)up(h[i][j][k].fi,-1);
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
294992 KB |
Output is correct |
2 |
Correct |
161 ms |
294980 KB |
Output is correct |
3 |
Correct |
170 ms |
295004 KB |
Output is correct |
4 |
Correct |
154 ms |
294992 KB |
Output is correct |
5 |
Correct |
157 ms |
294948 KB |
Output is correct |
6 |
Correct |
158 ms |
294992 KB |
Output is correct |
7 |
Correct |
158 ms |
294976 KB |
Output is correct |
8 |
Correct |
153 ms |
294992 KB |
Output is correct |
9 |
Correct |
155 ms |
294916 KB |
Output is correct |
10 |
Correct |
176 ms |
295008 KB |
Output is correct |
11 |
Correct |
154 ms |
295036 KB |
Output is correct |
12 |
Correct |
152 ms |
294960 KB |
Output is correct |
13 |
Correct |
158 ms |
294916 KB |
Output is correct |
14 |
Correct |
153 ms |
294992 KB |
Output is correct |
15 |
Correct |
153 ms |
294948 KB |
Output is correct |
16 |
Correct |
153 ms |
294884 KB |
Output is correct |
17 |
Correct |
155 ms |
294920 KB |
Output is correct |
18 |
Correct |
153 ms |
294984 KB |
Output is correct |
19 |
Correct |
157 ms |
294936 KB |
Output is correct |
20 |
Correct |
153 ms |
294912 KB |
Output is correct |
21 |
Correct |
155 ms |
294984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
294992 KB |
Output is correct |
2 |
Correct |
161 ms |
294980 KB |
Output is correct |
3 |
Correct |
170 ms |
295004 KB |
Output is correct |
4 |
Correct |
154 ms |
294992 KB |
Output is correct |
5 |
Correct |
157 ms |
294948 KB |
Output is correct |
6 |
Correct |
158 ms |
294992 KB |
Output is correct |
7 |
Correct |
158 ms |
294976 KB |
Output is correct |
8 |
Correct |
153 ms |
294992 KB |
Output is correct |
9 |
Correct |
155 ms |
294916 KB |
Output is correct |
10 |
Correct |
176 ms |
295008 KB |
Output is correct |
11 |
Correct |
154 ms |
295036 KB |
Output is correct |
12 |
Correct |
152 ms |
294960 KB |
Output is correct |
13 |
Correct |
158 ms |
294916 KB |
Output is correct |
14 |
Correct |
153 ms |
294992 KB |
Output is correct |
15 |
Correct |
153 ms |
294948 KB |
Output is correct |
16 |
Correct |
153 ms |
294884 KB |
Output is correct |
17 |
Correct |
155 ms |
294920 KB |
Output is correct |
18 |
Correct |
153 ms |
294984 KB |
Output is correct |
19 |
Correct |
157 ms |
294936 KB |
Output is correct |
20 |
Correct |
153 ms |
294912 KB |
Output is correct |
21 |
Correct |
155 ms |
294984 KB |
Output is correct |
22 |
Correct |
158 ms |
295456 KB |
Output is correct |
23 |
Correct |
155 ms |
295432 KB |
Output is correct |
24 |
Correct |
155 ms |
295452 KB |
Output is correct |
25 |
Correct |
162 ms |
295244 KB |
Output is correct |
26 |
Correct |
159 ms |
295268 KB |
Output is correct |
27 |
Correct |
156 ms |
295256 KB |
Output is correct |
28 |
Correct |
154 ms |
295176 KB |
Output is correct |
29 |
Correct |
153 ms |
295096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
294992 KB |
Output is correct |
2 |
Correct |
161 ms |
294980 KB |
Output is correct |
3 |
Correct |
170 ms |
295004 KB |
Output is correct |
4 |
Correct |
154 ms |
294992 KB |
Output is correct |
5 |
Correct |
157 ms |
294948 KB |
Output is correct |
6 |
Correct |
158 ms |
294992 KB |
Output is correct |
7 |
Correct |
158 ms |
294976 KB |
Output is correct |
8 |
Correct |
153 ms |
294992 KB |
Output is correct |
9 |
Correct |
155 ms |
294916 KB |
Output is correct |
10 |
Correct |
176 ms |
295008 KB |
Output is correct |
11 |
Correct |
154 ms |
295036 KB |
Output is correct |
12 |
Correct |
152 ms |
294960 KB |
Output is correct |
13 |
Correct |
158 ms |
294916 KB |
Output is correct |
14 |
Correct |
153 ms |
294992 KB |
Output is correct |
15 |
Correct |
153 ms |
294948 KB |
Output is correct |
16 |
Correct |
153 ms |
294884 KB |
Output is correct |
17 |
Correct |
158 ms |
295456 KB |
Output is correct |
18 |
Correct |
155 ms |
295432 KB |
Output is correct |
19 |
Correct |
155 ms |
295452 KB |
Output is correct |
20 |
Correct |
162 ms |
295244 KB |
Output is correct |
21 |
Correct |
159 ms |
295268 KB |
Output is correct |
22 |
Correct |
156 ms |
295256 KB |
Output is correct |
23 |
Correct |
154 ms |
295176 KB |
Output is correct |
24 |
Correct |
153 ms |
295096 KB |
Output is correct |
25 |
Correct |
155 ms |
294920 KB |
Output is correct |
26 |
Correct |
153 ms |
294984 KB |
Output is correct |
27 |
Correct |
157 ms |
294936 KB |
Output is correct |
28 |
Correct |
153 ms |
294912 KB |
Output is correct |
29 |
Correct |
155 ms |
294984 KB |
Output is correct |
30 |
Correct |
160 ms |
297936 KB |
Output is correct |
31 |
Correct |
163 ms |
297964 KB |
Output is correct |
32 |
Correct |
166 ms |
298100 KB |
Output is correct |
33 |
Correct |
165 ms |
296244 KB |
Output is correct |
34 |
Correct |
166 ms |
296856 KB |
Output is correct |
35 |
Correct |
165 ms |
297036 KB |
Output is correct |
36 |
Correct |
167 ms |
296940 KB |
Output is correct |
37 |
Correct |
168 ms |
296908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
294992 KB |
Output is correct |
2 |
Correct |
161 ms |
294980 KB |
Output is correct |
3 |
Correct |
170 ms |
295004 KB |
Output is correct |
4 |
Correct |
154 ms |
294992 KB |
Output is correct |
5 |
Correct |
157 ms |
294948 KB |
Output is correct |
6 |
Correct |
158 ms |
294992 KB |
Output is correct |
7 |
Correct |
158 ms |
294976 KB |
Output is correct |
8 |
Correct |
153 ms |
294992 KB |
Output is correct |
9 |
Correct |
155 ms |
294916 KB |
Output is correct |
10 |
Correct |
176 ms |
295008 KB |
Output is correct |
11 |
Correct |
154 ms |
295036 KB |
Output is correct |
12 |
Correct |
152 ms |
294960 KB |
Output is correct |
13 |
Correct |
158 ms |
294916 KB |
Output is correct |
14 |
Correct |
153 ms |
294992 KB |
Output is correct |
15 |
Correct |
153 ms |
294948 KB |
Output is correct |
16 |
Correct |
153 ms |
294884 KB |
Output is correct |
17 |
Correct |
158 ms |
295456 KB |
Output is correct |
18 |
Correct |
155 ms |
295432 KB |
Output is correct |
19 |
Correct |
155 ms |
295452 KB |
Output is correct |
20 |
Correct |
162 ms |
295244 KB |
Output is correct |
21 |
Correct |
159 ms |
295268 KB |
Output is correct |
22 |
Correct |
156 ms |
295256 KB |
Output is correct |
23 |
Correct |
154 ms |
295176 KB |
Output is correct |
24 |
Correct |
153 ms |
295096 KB |
Output is correct |
25 |
Correct |
160 ms |
297936 KB |
Output is correct |
26 |
Correct |
163 ms |
297964 KB |
Output is correct |
27 |
Correct |
166 ms |
298100 KB |
Output is correct |
28 |
Correct |
165 ms |
296244 KB |
Output is correct |
29 |
Correct |
166 ms |
296856 KB |
Output is correct |
30 |
Correct |
165 ms |
297036 KB |
Output is correct |
31 |
Correct |
167 ms |
296940 KB |
Output is correct |
32 |
Correct |
168 ms |
296908 KB |
Output is correct |
33 |
Correct |
155 ms |
294920 KB |
Output is correct |
34 |
Correct |
153 ms |
294984 KB |
Output is correct |
35 |
Correct |
157 ms |
294936 KB |
Output is correct |
36 |
Correct |
153 ms |
294912 KB |
Output is correct |
37 |
Correct |
155 ms |
294984 KB |
Output is correct |
38 |
Correct |
254 ms |
323064 KB |
Output is correct |
39 |
Correct |
229 ms |
315484 KB |
Output is correct |
40 |
Correct |
215 ms |
315372 KB |
Output is correct |
41 |
Correct |
199 ms |
307788 KB |
Output is correct |
42 |
Correct |
277 ms |
332660 KB |
Output is correct |
43 |
Correct |
278 ms |
332720 KB |
Output is correct |
44 |
Correct |
286 ms |
332996 KB |
Output is correct |
45 |
Correct |
273 ms |
330700 KB |
Output is correct |
46 |
Correct |
215 ms |
307528 KB |
Output is correct |
47 |
Correct |
236 ms |
309988 KB |
Output is correct |
48 |
Correct |
294 ms |
318800 KB |
Output is correct |
49 |
Correct |
304 ms |
320716 KB |
Output is correct |
50 |
Correct |
247 ms |
307904 KB |
Output is correct |
51 |
Correct |
225 ms |
307832 KB |
Output is correct |
52 |
Correct |
297 ms |
318336 KB |
Output is correct |
53 |
Correct |
298 ms |
319364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
157 ms |
295244 KB |
Output is correct |
2 |
Correct |
156 ms |
295452 KB |
Output is correct |
3 |
Correct |
156 ms |
295072 KB |
Output is correct |
4 |
Correct |
155 ms |
294908 KB |
Output is correct |
5 |
Correct |
171 ms |
295320 KB |
Output is correct |
6 |
Correct |
160 ms |
295288 KB |
Output is correct |
7 |
Correct |
162 ms |
295344 KB |
Output is correct |
8 |
Correct |
153 ms |
295244 KB |
Output is correct |
9 |
Correct |
157 ms |
295368 KB |
Output is correct |
10 |
Correct |
157 ms |
294952 KB |
Output is correct |
11 |
Correct |
155 ms |
295136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
294920 KB |
Output is correct |
2 |
Correct |
153 ms |
294984 KB |
Output is correct |
3 |
Correct |
157 ms |
294936 KB |
Output is correct |
4 |
Correct |
153 ms |
294912 KB |
Output is correct |
5 |
Correct |
155 ms |
294984 KB |
Output is correct |
6 |
Correct |
157 ms |
294908 KB |
Output is correct |
7 |
Correct |
576 ms |
362444 KB |
Output is correct |
8 |
Correct |
1105 ms |
441308 KB |
Output is correct |
9 |
Correct |
1110 ms |
442200 KB |
Output is correct |
10 |
Correct |
1144 ms |
442044 KB |
Output is correct |
11 |
Correct |
287 ms |
319316 KB |
Output is correct |
12 |
Correct |
406 ms |
341352 KB |
Output is correct |
13 |
Correct |
418 ms |
344228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
294992 KB |
Output is correct |
2 |
Correct |
161 ms |
294980 KB |
Output is correct |
3 |
Correct |
170 ms |
295004 KB |
Output is correct |
4 |
Correct |
154 ms |
294992 KB |
Output is correct |
5 |
Correct |
157 ms |
294948 KB |
Output is correct |
6 |
Correct |
158 ms |
294992 KB |
Output is correct |
7 |
Correct |
158 ms |
294976 KB |
Output is correct |
8 |
Correct |
153 ms |
294992 KB |
Output is correct |
9 |
Correct |
155 ms |
294916 KB |
Output is correct |
10 |
Correct |
176 ms |
295008 KB |
Output is correct |
11 |
Correct |
154 ms |
295036 KB |
Output is correct |
12 |
Correct |
152 ms |
294960 KB |
Output is correct |
13 |
Correct |
158 ms |
294916 KB |
Output is correct |
14 |
Correct |
153 ms |
294992 KB |
Output is correct |
15 |
Correct |
153 ms |
294948 KB |
Output is correct |
16 |
Correct |
153 ms |
294884 KB |
Output is correct |
17 |
Correct |
158 ms |
295456 KB |
Output is correct |
18 |
Correct |
155 ms |
295432 KB |
Output is correct |
19 |
Correct |
155 ms |
295452 KB |
Output is correct |
20 |
Correct |
162 ms |
295244 KB |
Output is correct |
21 |
Correct |
159 ms |
295268 KB |
Output is correct |
22 |
Correct |
156 ms |
295256 KB |
Output is correct |
23 |
Correct |
154 ms |
295176 KB |
Output is correct |
24 |
Correct |
153 ms |
295096 KB |
Output is correct |
25 |
Correct |
160 ms |
297936 KB |
Output is correct |
26 |
Correct |
163 ms |
297964 KB |
Output is correct |
27 |
Correct |
166 ms |
298100 KB |
Output is correct |
28 |
Correct |
165 ms |
296244 KB |
Output is correct |
29 |
Correct |
166 ms |
296856 KB |
Output is correct |
30 |
Correct |
165 ms |
297036 KB |
Output is correct |
31 |
Correct |
167 ms |
296940 KB |
Output is correct |
32 |
Correct |
168 ms |
296908 KB |
Output is correct |
33 |
Correct |
254 ms |
323064 KB |
Output is correct |
34 |
Correct |
229 ms |
315484 KB |
Output is correct |
35 |
Correct |
215 ms |
315372 KB |
Output is correct |
36 |
Correct |
199 ms |
307788 KB |
Output is correct |
37 |
Correct |
277 ms |
332660 KB |
Output is correct |
38 |
Correct |
278 ms |
332720 KB |
Output is correct |
39 |
Correct |
286 ms |
332996 KB |
Output is correct |
40 |
Correct |
273 ms |
330700 KB |
Output is correct |
41 |
Correct |
215 ms |
307528 KB |
Output is correct |
42 |
Correct |
236 ms |
309988 KB |
Output is correct |
43 |
Correct |
294 ms |
318800 KB |
Output is correct |
44 |
Correct |
304 ms |
320716 KB |
Output is correct |
45 |
Correct |
247 ms |
307904 KB |
Output is correct |
46 |
Correct |
225 ms |
307832 KB |
Output is correct |
47 |
Correct |
297 ms |
318336 KB |
Output is correct |
48 |
Correct |
298 ms |
319364 KB |
Output is correct |
49 |
Correct |
157 ms |
295244 KB |
Output is correct |
50 |
Correct |
156 ms |
295452 KB |
Output is correct |
51 |
Correct |
156 ms |
295072 KB |
Output is correct |
52 |
Correct |
155 ms |
294908 KB |
Output is correct |
53 |
Correct |
171 ms |
295320 KB |
Output is correct |
54 |
Correct |
160 ms |
295288 KB |
Output is correct |
55 |
Correct |
162 ms |
295344 KB |
Output is correct |
56 |
Correct |
153 ms |
295244 KB |
Output is correct |
57 |
Correct |
157 ms |
295368 KB |
Output is correct |
58 |
Correct |
157 ms |
294952 KB |
Output is correct |
59 |
Correct |
155 ms |
295136 KB |
Output is correct |
60 |
Correct |
157 ms |
294908 KB |
Output is correct |
61 |
Correct |
576 ms |
362444 KB |
Output is correct |
62 |
Correct |
1105 ms |
441308 KB |
Output is correct |
63 |
Correct |
1110 ms |
442200 KB |
Output is correct |
64 |
Correct |
1144 ms |
442044 KB |
Output is correct |
65 |
Correct |
287 ms |
319316 KB |
Output is correct |
66 |
Correct |
406 ms |
341352 KB |
Output is correct |
67 |
Correct |
418 ms |
344228 KB |
Output is correct |
68 |
Correct |
155 ms |
294920 KB |
Output is correct |
69 |
Correct |
153 ms |
294984 KB |
Output is correct |
70 |
Correct |
157 ms |
294936 KB |
Output is correct |
71 |
Correct |
153 ms |
294912 KB |
Output is correct |
72 |
Correct |
155 ms |
294984 KB |
Output is correct |
73 |
Correct |
1649 ms |
603860 KB |
Output is correct |
74 |
Correct |
1426 ms |
505992 KB |
Output is correct |
75 |
Correct |
927 ms |
505976 KB |
Output is correct |
76 |
Correct |
793 ms |
408176 KB |
Output is correct |
77 |
Correct |
2405 ms |
737824 KB |
Output is correct |
78 |
Correct |
1380 ms |
476796 KB |
Output is correct |
79 |
Correct |
1421 ms |
474532 KB |
Output is correct |
80 |
Correct |
2228 ms |
576732 KB |
Output is correct |
81 |
Correct |
1435 ms |
465740 KB |
Output is correct |
82 |
Correct |
1817 ms |
523856 KB |
Output is correct |
83 |
Correct |
2310 ms |
580348 KB |
Output is correct |
84 |
Correct |
1347 ms |
454972 KB |
Output is correct |
85 |
Correct |
2213 ms |
563948 KB |
Output is correct |
86 |
Correct |
2171 ms |
555632 KB |
Output is correct |
87 |
Correct |
1448 ms |
560368 KB |
Output is correct |
88 |
Correct |
2402 ms |
737388 KB |
Output is correct |
89 |
Correct |
2383 ms |
737696 KB |
Output is correct |
90 |
Correct |
2406 ms |
737872 KB |
Output is correct |