#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
#define all(a) a.begin(), a.end()
typedef short int sint;
const sint MX=2505;
sint n, m;
vector<sint> difW[MX][MX];
vector<sint> difH[MX][MX];
sint maxW[MX][MX];
sint maxH[MX][MX];
vector<pair<sint,sint>> lastW[2][MX];
vector<pair<sint,sint>> lastH[MX];
long long count_rectangles(vector<vi> a) {
n = a.sz; m = a[0].sz;
RE(i,n) {
stack<sint> stck;
RE(j,m) {
while(!stck.empty() && a[i][stck.top()] < a[i][j]) {
stck.pop();
if(!stck.empty()) {
difH[i][stck.top()+1].pb(j-stck.top()-1);
}
}
if(!stck.empty() && a[i][stck.top()] == a[i][j])
stck.pop();
stck.push(j);
}
}
RE(j,m) {
stack<sint> stck;
RE(i,n) {
while(!stck.empty() && a[stck.top()][j] < a[i][j]) {
stck.pop();
if(!stck.empty()) {
difW[stck.top()+1][j].pb(i-stck.top()-1);
}
}
if(!stck.empty() && a[stck.top()][j] == a[i][j])
stck.pop();
stck.push(i);
}
}
ll ans = 0;
RE(i,n) RE(j,m) maxW[i][j] = maxH[i][j] = 0;
REV(i,0,n) {
REV(j,0,m) {
FOR(w,difW[i][j]) {
maxH[i][w]++;
lastH[j].pb({w,maxH[i][w]});
}
FOR(p,lastH[j+1]) {
if(maxH[i][p.fi] == p.se)
maxH[i][p.fi] = 0;
}
lastH[j+1].clear();
FOR(h,difH[i][j]) {
maxW[j][h]++;
lastW[i%2][j].pb({h,maxW[j][h]});
}
FOR(p,lastW[(i+1)%2][j]) {
if(maxW[j][p.fi] == p.se)
maxW[j][p.fi] = 0;
}
lastW[(i+1)%2][j].clear();
FOR(w,difW[i][j]) FOR(h,difH[i][j]) {
if(maxH[i][w] < h) break;
if(maxW[j][h] >= w)
ans++;
}
}
lastH[0].clear();
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
295288 KB |
Output is correct |
2 |
Correct |
206 ms |
295544 KB |
Output is correct |
3 |
Correct |
207 ms |
295544 KB |
Output is correct |
4 |
Correct |
206 ms |
295544 KB |
Output is correct |
5 |
Correct |
198 ms |
295416 KB |
Output is correct |
6 |
Correct |
199 ms |
295544 KB |
Output is correct |
7 |
Correct |
205 ms |
295416 KB |
Output is correct |
8 |
Correct |
204 ms |
295416 KB |
Output is correct |
9 |
Correct |
199 ms |
295544 KB |
Output is correct |
10 |
Correct |
204 ms |
295544 KB |
Output is correct |
11 |
Correct |
202 ms |
295544 KB |
Output is correct |
12 |
Correct |
205 ms |
295544 KB |
Output is correct |
13 |
Correct |
201 ms |
295160 KB |
Output is correct |
14 |
Correct |
198 ms |
295256 KB |
Output is correct |
15 |
Correct |
202 ms |
295288 KB |
Output is correct |
16 |
Correct |
205 ms |
295416 KB |
Output is correct |
17 |
Correct |
197 ms |
295288 KB |
Output is correct |
18 |
Correct |
200 ms |
295288 KB |
Output is correct |
19 |
Correct |
204 ms |
295544 KB |
Output is correct |
20 |
Correct |
201 ms |
295416 KB |
Output is correct |
21 |
Correct |
200 ms |
295288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
295288 KB |
Output is correct |
2 |
Correct |
206 ms |
295544 KB |
Output is correct |
3 |
Correct |
207 ms |
295544 KB |
Output is correct |
4 |
Correct |
206 ms |
295544 KB |
Output is correct |
5 |
Correct |
198 ms |
295416 KB |
Output is correct |
6 |
Correct |
199 ms |
295544 KB |
Output is correct |
7 |
Correct |
205 ms |
295416 KB |
Output is correct |
8 |
Correct |
204 ms |
295416 KB |
Output is correct |
9 |
Correct |
199 ms |
295544 KB |
Output is correct |
10 |
Correct |
204 ms |
295544 KB |
Output is correct |
11 |
Correct |
202 ms |
295544 KB |
Output is correct |
12 |
Correct |
205 ms |
295544 KB |
Output is correct |
13 |
Correct |
201 ms |
295160 KB |
Output is correct |
14 |
Correct |
198 ms |
295256 KB |
Output is correct |
15 |
Correct |
202 ms |
295288 KB |
Output is correct |
16 |
Correct |
205 ms |
295416 KB |
Output is correct |
17 |
Correct |
202 ms |
296368 KB |
Output is correct |
18 |
Correct |
199 ms |
296312 KB |
Output is correct |
19 |
Correct |
211 ms |
296312 KB |
Output is correct |
20 |
Correct |
200 ms |
296184 KB |
Output is correct |
21 |
Correct |
202 ms |
296184 KB |
Output is correct |
22 |
Correct |
207 ms |
296184 KB |
Output is correct |
23 |
Correct |
201 ms |
296184 KB |
Output is correct |
24 |
Correct |
201 ms |
296056 KB |
Output is correct |
25 |
Correct |
197 ms |
295288 KB |
Output is correct |
26 |
Correct |
200 ms |
295288 KB |
Output is correct |
27 |
Correct |
204 ms |
295544 KB |
Output is correct |
28 |
Correct |
201 ms |
295416 KB |
Output is correct |
29 |
Correct |
200 ms |
295288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
295288 KB |
Output is correct |
2 |
Correct |
206 ms |
295544 KB |
Output is correct |
3 |
Correct |
207 ms |
295544 KB |
Output is correct |
4 |
Correct |
206 ms |
295544 KB |
Output is correct |
5 |
Correct |
198 ms |
295416 KB |
Output is correct |
6 |
Correct |
199 ms |
295544 KB |
Output is correct |
7 |
Correct |
205 ms |
295416 KB |
Output is correct |
8 |
Correct |
204 ms |
295416 KB |
Output is correct |
9 |
Correct |
199 ms |
295544 KB |
Output is correct |
10 |
Correct |
204 ms |
295544 KB |
Output is correct |
11 |
Correct |
202 ms |
295544 KB |
Output is correct |
12 |
Correct |
205 ms |
295544 KB |
Output is correct |
13 |
Correct |
201 ms |
295160 KB |
Output is correct |
14 |
Correct |
198 ms |
295256 KB |
Output is correct |
15 |
Correct |
202 ms |
295288 KB |
Output is correct |
16 |
Correct |
205 ms |
295416 KB |
Output is correct |
17 |
Correct |
202 ms |
296368 KB |
Output is correct |
18 |
Correct |
199 ms |
296312 KB |
Output is correct |
19 |
Correct |
211 ms |
296312 KB |
Output is correct |
20 |
Correct |
200 ms |
296184 KB |
Output is correct |
21 |
Correct |
202 ms |
296184 KB |
Output is correct |
22 |
Correct |
207 ms |
296184 KB |
Output is correct |
23 |
Correct |
201 ms |
296184 KB |
Output is correct |
24 |
Correct |
201 ms |
296056 KB |
Output is correct |
25 |
Correct |
217 ms |
299776 KB |
Output is correct |
26 |
Correct |
209 ms |
299896 KB |
Output is correct |
27 |
Correct |
211 ms |
299768 KB |
Output is correct |
28 |
Correct |
206 ms |
298104 KB |
Output is correct |
29 |
Correct |
222 ms |
298744 KB |
Output is correct |
30 |
Correct |
212 ms |
298616 KB |
Output is correct |
31 |
Correct |
214 ms |
298616 KB |
Output is correct |
32 |
Correct |
214 ms |
298488 KB |
Output is correct |
33 |
Correct |
197 ms |
295288 KB |
Output is correct |
34 |
Correct |
200 ms |
295288 KB |
Output is correct |
35 |
Correct |
204 ms |
295544 KB |
Output is correct |
36 |
Correct |
201 ms |
295416 KB |
Output is correct |
37 |
Correct |
200 ms |
295288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
295288 KB |
Output is correct |
2 |
Correct |
206 ms |
295544 KB |
Output is correct |
3 |
Correct |
207 ms |
295544 KB |
Output is correct |
4 |
Correct |
206 ms |
295544 KB |
Output is correct |
5 |
Correct |
198 ms |
295416 KB |
Output is correct |
6 |
Correct |
199 ms |
295544 KB |
Output is correct |
7 |
Correct |
205 ms |
295416 KB |
Output is correct |
8 |
Correct |
204 ms |
295416 KB |
Output is correct |
9 |
Correct |
199 ms |
295544 KB |
Output is correct |
10 |
Correct |
204 ms |
295544 KB |
Output is correct |
11 |
Correct |
202 ms |
295544 KB |
Output is correct |
12 |
Correct |
205 ms |
295544 KB |
Output is correct |
13 |
Correct |
201 ms |
295160 KB |
Output is correct |
14 |
Correct |
198 ms |
295256 KB |
Output is correct |
15 |
Correct |
202 ms |
295288 KB |
Output is correct |
16 |
Correct |
205 ms |
295416 KB |
Output is correct |
17 |
Correct |
202 ms |
296368 KB |
Output is correct |
18 |
Correct |
199 ms |
296312 KB |
Output is correct |
19 |
Correct |
211 ms |
296312 KB |
Output is correct |
20 |
Correct |
200 ms |
296184 KB |
Output is correct |
21 |
Correct |
202 ms |
296184 KB |
Output is correct |
22 |
Correct |
207 ms |
296184 KB |
Output is correct |
23 |
Correct |
201 ms |
296184 KB |
Output is correct |
24 |
Correct |
201 ms |
296056 KB |
Output is correct |
25 |
Correct |
217 ms |
299776 KB |
Output is correct |
26 |
Correct |
209 ms |
299896 KB |
Output is correct |
27 |
Correct |
211 ms |
299768 KB |
Output is correct |
28 |
Correct |
206 ms |
298104 KB |
Output is correct |
29 |
Correct |
222 ms |
298744 KB |
Output is correct |
30 |
Correct |
212 ms |
298616 KB |
Output is correct |
31 |
Correct |
214 ms |
298616 KB |
Output is correct |
32 |
Correct |
214 ms |
298488 KB |
Output is correct |
33 |
Correct |
283 ms |
321272 KB |
Output is correct |
34 |
Correct |
269 ms |
316280 KB |
Output is correct |
35 |
Correct |
265 ms |
316280 KB |
Output is correct |
36 |
Correct |
244 ms |
310648 KB |
Output is correct |
37 |
Correct |
341 ms |
337016 KB |
Output is correct |
38 |
Correct |
339 ms |
336764 KB |
Output is correct |
39 |
Correct |
349 ms |
336760 KB |
Output is correct |
40 |
Correct |
335 ms |
334328 KB |
Output is correct |
41 |
Correct |
272 ms |
313848 KB |
Output is correct |
42 |
Correct |
319 ms |
316408 KB |
Output is correct |
43 |
Correct |
381 ms |
321532 KB |
Output is correct |
44 |
Correct |
372 ms |
321660 KB |
Output is correct |
45 |
Correct |
284 ms |
311676 KB |
Output is correct |
46 |
Correct |
289 ms |
310008 KB |
Output is correct |
47 |
Correct |
356 ms |
320248 KB |
Output is correct |
48 |
Correct |
361 ms |
320508 KB |
Output is correct |
49 |
Correct |
197 ms |
295288 KB |
Output is correct |
50 |
Correct |
200 ms |
295288 KB |
Output is correct |
51 |
Correct |
204 ms |
295544 KB |
Output is correct |
52 |
Correct |
201 ms |
295416 KB |
Output is correct |
53 |
Correct |
200 ms |
295288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
305864 KB |
Output is correct |
2 |
Correct |
204 ms |
304248 KB |
Output is correct |
3 |
Correct |
202 ms |
295332 KB |
Output is correct |
4 |
Correct |
205 ms |
295288 KB |
Output is correct |
5 |
Correct |
219 ms |
304504 KB |
Output is correct |
6 |
Correct |
212 ms |
304248 KB |
Output is correct |
7 |
Correct |
215 ms |
304380 KB |
Output is correct |
8 |
Correct |
215 ms |
303864 KB |
Output is correct |
9 |
Correct |
212 ms |
303608 KB |
Output is correct |
10 |
Correct |
204 ms |
300408 KB |
Output is correct |
11 |
Correct |
207 ms |
302968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
295288 KB |
Output is correct |
2 |
Correct |
680 ms |
379224 KB |
Output is correct |
3 |
Correct |
1265 ms |
466168 KB |
Output is correct |
4 |
Correct |
1299 ms |
466680 KB |
Output is correct |
5 |
Correct |
1253 ms |
467064 KB |
Output is correct |
6 |
Correct |
311 ms |
331512 KB |
Output is correct |
7 |
Correct |
422 ms |
365816 KB |
Output is correct |
8 |
Correct |
438 ms |
368888 KB |
Output is correct |
9 |
Correct |
197 ms |
295288 KB |
Output is correct |
10 |
Correct |
200 ms |
295288 KB |
Output is correct |
11 |
Correct |
204 ms |
295544 KB |
Output is correct |
12 |
Correct |
201 ms |
295416 KB |
Output is correct |
13 |
Correct |
200 ms |
295288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
295288 KB |
Output is correct |
2 |
Correct |
206 ms |
295544 KB |
Output is correct |
3 |
Correct |
207 ms |
295544 KB |
Output is correct |
4 |
Correct |
206 ms |
295544 KB |
Output is correct |
5 |
Correct |
198 ms |
295416 KB |
Output is correct |
6 |
Correct |
199 ms |
295544 KB |
Output is correct |
7 |
Correct |
205 ms |
295416 KB |
Output is correct |
8 |
Correct |
204 ms |
295416 KB |
Output is correct |
9 |
Correct |
199 ms |
295544 KB |
Output is correct |
10 |
Correct |
204 ms |
295544 KB |
Output is correct |
11 |
Correct |
202 ms |
295544 KB |
Output is correct |
12 |
Correct |
205 ms |
295544 KB |
Output is correct |
13 |
Correct |
201 ms |
295160 KB |
Output is correct |
14 |
Correct |
198 ms |
295256 KB |
Output is correct |
15 |
Correct |
202 ms |
295288 KB |
Output is correct |
16 |
Correct |
205 ms |
295416 KB |
Output is correct |
17 |
Correct |
202 ms |
296368 KB |
Output is correct |
18 |
Correct |
199 ms |
296312 KB |
Output is correct |
19 |
Correct |
211 ms |
296312 KB |
Output is correct |
20 |
Correct |
200 ms |
296184 KB |
Output is correct |
21 |
Correct |
202 ms |
296184 KB |
Output is correct |
22 |
Correct |
207 ms |
296184 KB |
Output is correct |
23 |
Correct |
201 ms |
296184 KB |
Output is correct |
24 |
Correct |
201 ms |
296056 KB |
Output is correct |
25 |
Correct |
217 ms |
299776 KB |
Output is correct |
26 |
Correct |
209 ms |
299896 KB |
Output is correct |
27 |
Correct |
211 ms |
299768 KB |
Output is correct |
28 |
Correct |
206 ms |
298104 KB |
Output is correct |
29 |
Correct |
222 ms |
298744 KB |
Output is correct |
30 |
Correct |
212 ms |
298616 KB |
Output is correct |
31 |
Correct |
214 ms |
298616 KB |
Output is correct |
32 |
Correct |
214 ms |
298488 KB |
Output is correct |
33 |
Correct |
283 ms |
321272 KB |
Output is correct |
34 |
Correct |
269 ms |
316280 KB |
Output is correct |
35 |
Correct |
265 ms |
316280 KB |
Output is correct |
36 |
Correct |
244 ms |
310648 KB |
Output is correct |
37 |
Correct |
341 ms |
337016 KB |
Output is correct |
38 |
Correct |
339 ms |
336764 KB |
Output is correct |
39 |
Correct |
349 ms |
336760 KB |
Output is correct |
40 |
Correct |
335 ms |
334328 KB |
Output is correct |
41 |
Correct |
272 ms |
313848 KB |
Output is correct |
42 |
Correct |
319 ms |
316408 KB |
Output is correct |
43 |
Correct |
381 ms |
321532 KB |
Output is correct |
44 |
Correct |
372 ms |
321660 KB |
Output is correct |
45 |
Correct |
284 ms |
311676 KB |
Output is correct |
46 |
Correct |
289 ms |
310008 KB |
Output is correct |
47 |
Correct |
356 ms |
320248 KB |
Output is correct |
48 |
Correct |
361 ms |
320508 KB |
Output is correct |
49 |
Correct |
208 ms |
305864 KB |
Output is correct |
50 |
Correct |
204 ms |
304248 KB |
Output is correct |
51 |
Correct |
202 ms |
295332 KB |
Output is correct |
52 |
Correct |
205 ms |
295288 KB |
Output is correct |
53 |
Correct |
219 ms |
304504 KB |
Output is correct |
54 |
Correct |
212 ms |
304248 KB |
Output is correct |
55 |
Correct |
215 ms |
304380 KB |
Output is correct |
56 |
Correct |
215 ms |
303864 KB |
Output is correct |
57 |
Correct |
212 ms |
303608 KB |
Output is correct |
58 |
Correct |
204 ms |
300408 KB |
Output is correct |
59 |
Correct |
207 ms |
302968 KB |
Output is correct |
60 |
Correct |
202 ms |
295288 KB |
Output is correct |
61 |
Correct |
680 ms |
379224 KB |
Output is correct |
62 |
Correct |
1265 ms |
466168 KB |
Output is correct |
63 |
Correct |
1299 ms |
466680 KB |
Output is correct |
64 |
Correct |
1253 ms |
467064 KB |
Output is correct |
65 |
Correct |
311 ms |
331512 KB |
Output is correct |
66 |
Correct |
422 ms |
365816 KB |
Output is correct |
67 |
Correct |
438 ms |
368888 KB |
Output is correct |
68 |
Correct |
1500 ms |
565268 KB |
Output is correct |
69 |
Correct |
1317 ms |
492792 KB |
Output is correct |
70 |
Correct |
1012 ms |
493040 KB |
Output is correct |
71 |
Correct |
812 ms |
420732 KB |
Output is correct |
72 |
Correct |
2478 ms |
760976 KB |
Output is correct |
73 |
Correct |
1619 ms |
462200 KB |
Output is correct |
74 |
Correct |
1676 ms |
475128 KB |
Output is correct |
75 |
Correct |
2572 ms |
565372 KB |
Output is correct |
76 |
Correct |
1675 ms |
462456 KB |
Output is correct |
77 |
Correct |
2113 ms |
516764 KB |
Output is correct |
78 |
Correct |
2654 ms |
565880 KB |
Output is correct |
79 |
Correct |
1550 ms |
452984 KB |
Output is correct |
80 |
Correct |
2546 ms |
551800 KB |
Output is correct |
81 |
Correct |
2465 ms |
544388 KB |
Output is correct |
82 |
Correct |
1517 ms |
584696 KB |
Output is correct |
83 |
Correct |
2418 ms |
760752 KB |
Output is correct |
84 |
Correct |
2467 ms |
761104 KB |
Output is correct |
85 |
Correct |
2454 ms |
760824 KB |
Output is correct |
86 |
Correct |
197 ms |
295288 KB |
Output is correct |
87 |
Correct |
200 ms |
295288 KB |
Output is correct |
88 |
Correct |
204 ms |
295544 KB |
Output is correct |
89 |
Correct |
201 ms |
295416 KB |
Output is correct |
90 |
Correct |
200 ms |
295288 KB |
Output is correct |