//
#ifndef __SIZEOF_INT128__
#define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
string name{""};
time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
duration<float, std::milli> dur;
Timer() = default;
Timer(string nm): name(nm) {}
~Timer() {
end = high_resolution_clock::now(); dur= end - start;
cout << "@" << name << "> " << dur.count() << " ms" << '\n';
}
};
template <typename T = int> inline T in()
{
static T x;
std::cin >> x;
return x;
}
std::string yn(bool b)
{
if(b) return "YES\n";
else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
for(const auto& i : wek)out << i << ' ';
return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
out << '{'<<par.first<<", "<<par.second<<"}";
return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
template <typename T>
vector <int> ostw(T b, T e, bool r)
{
vector <int> o;
vector <pair <int, int>> k{{1e9, -1}};
int j(0);
for(auto i(b); i != e; ++i){
while(k.back().first < *i || (k.back().first == *i && !r))k.pop_back();
o.pb(k.back().second);
k.pb(*i, j++);
}
return o;
}
constexpr int maxn = 2503, pol = 1<<12;
array <array <int, maxn>, maxn> r, l, u, d;
array <array <int, pol*2>, maxn> mr, ml, mu, md;
template <typename T>
void trurev(T b, T e, int n)
{
reverse(b, e);
for(auto i(b); i != e; ++i)if(*i != -1)*i = n-1-*i;
}
struct rect{int x1, y1, x2, y2;};
bool operator<(rect a, rect b)
{
if(a.x1 != b.x1)return a.x1 < b.x1;
if(a.y1 != b.y1)return a.y1 < b.y1;
if(a.x2 != b.x2)return a.x2 < b.x2;
return a.y2 < b.y2;
}
int maks(const array <int, pol*2>& tr, int a, int b)
{
a += pol; b += pol;
int s(-1e9);
while(a+1 != b){
if(a % 2 == 0)s = max(s, tr[a+1]);
if(b % 2 == 1)s = max(s, tr[b-1]);
a /= 2;
b /= 2;
}
return s;
}
int mini(const array <int, pol*2>& tr, int a, int b)
{
a += pol; b += pol;
int s(1e9);
while(a+1 != b){
if(a % 2 == 0)s = min(s, tr[a+1]);
if(b % 2 == 1)s = min(s, tr[b-1]);
a /= 2;
b /= 2;
}
return s;
}
ll count_rectangles(vector <vector <int>> a)
{
int n(sz(a)), m(sz(a[0]));
rep(i, 0, n){
vector <int> dl(ostw(all(a[i]), 0)), dr(ostw(rall(a[i]), 0)), dml(ostw(all(a[i]), 1)), dmr(ostw(rall(a[i]), 1));
trurev(all(dr), m);
trurev(all(dmr), m);
rep(j, 0, m)l[i][j] = dl[j];
rep(j, 0, m)r[i][j] = dr[j];
rep(j, 0, m)ml[j][i+pol] = dml[j];
rep(j, 0, m)mr[j][i+pol] = dmr[j] == -1 ? 1e9 : dmr[j];
}
rep(i, 0, m){
vector <int> v(n);
rep(j, 0, n)v[j] = a[j][i];
vector <int> du(ostw(all(v), 0)), dd(ostw(rall(v), 0)), dmu(ostw(all(v), 1)), dmd(ostw(rall(v), 1));
trurev(all(dd), n);
trurev(all(dmd), n);
rep(j, 0, n)u[j][i] = du[j];
rep(j, 0, n)d[j][i] = dd[j];
rep(j, 0, n)mu[j][i+pol] = dmu[j];
rep(j, 0, n)md[j][i+pol] = dmd[j] == -1 ? 1e9 : dmd[j];
}
rep(i, 0, n)per(j, pol-1, 0)mu[i][j] = max(mu[i][j*2], mu[i][j*2+1]);
rep(i, 0, n)per(j, pol-1, 0)md[i][j] = min(md[i][j*2], md[i][j*2+1]);
rep(i, 0, m)per(j, pol-1, 0)ml[i][j] = max(ml[i][j*2], ml[i][j*2+1]);
rep(i, 0, m)per(j, pol-1, 0)mr[i][j] = min(mr[i][j*2], mr[i][j*2+1]);
set <rect> S;
rep(i, 0, n)rep(j, 0, m)if(~l[i][j] && ~u[i][j] && ~r[i][j] && ~d[i][j])S.insert({u[i][j], l[i][j], d[i][j], r[i][j]});
int o(0);
for(auto [x1, y1, x2, y2]: S){
// cerr << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << " =/= "<< ' ' << maks(mu[x2], y1, y2) << ' ' << maks(ml[y2], x1, x2) << ' ' << mini(md[x1], y1, y2) << ' ' << mini(mr[y1], x1, x2) << '\n';
o += mini(md[x1], y1, y2) >= x2 && mini(mr[y1], x1, x2) >= y2 && maks(mu[x2], y1, y2) <= x1 && maks(ml[y2], x1, x2) <= y1;
}
return o;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16728 KB |
Output is correct |
2 |
Correct |
3 ms |
16968 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
2 ms |
16984 KB |
Output is correct |
5 |
Correct |
2 ms |
16732 KB |
Output is correct |
6 |
Correct |
2 ms |
16988 KB |
Output is correct |
7 |
Correct |
2 ms |
16828 KB |
Output is correct |
8 |
Correct |
2 ms |
16732 KB |
Output is correct |
9 |
Correct |
2 ms |
16988 KB |
Output is correct |
10 |
Correct |
3 ms |
16988 KB |
Output is correct |
11 |
Correct |
2 ms |
16988 KB |
Output is correct |
12 |
Correct |
3 ms |
16988 KB |
Output is correct |
13 |
Correct |
1 ms |
14680 KB |
Output is correct |
14 |
Correct |
2 ms |
16732 KB |
Output is correct |
15 |
Correct |
2 ms |
16736 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
2 ms |
14684 KB |
Output is correct |
18 |
Correct |
2 ms |
14684 KB |
Output is correct |
19 |
Correct |
2 ms |
16732 KB |
Output is correct |
20 |
Correct |
2 ms |
16732 KB |
Output is correct |
21 |
Correct |
2 ms |
16732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16728 KB |
Output is correct |
2 |
Correct |
3 ms |
16968 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
2 ms |
16984 KB |
Output is correct |
5 |
Correct |
2 ms |
16732 KB |
Output is correct |
6 |
Correct |
2 ms |
16988 KB |
Output is correct |
7 |
Correct |
2 ms |
16828 KB |
Output is correct |
8 |
Correct |
2 ms |
16732 KB |
Output is correct |
9 |
Correct |
2 ms |
16988 KB |
Output is correct |
10 |
Correct |
3 ms |
16988 KB |
Output is correct |
11 |
Correct |
2 ms |
16988 KB |
Output is correct |
12 |
Correct |
3 ms |
16988 KB |
Output is correct |
13 |
Correct |
1 ms |
14680 KB |
Output is correct |
14 |
Correct |
2 ms |
16732 KB |
Output is correct |
15 |
Correct |
2 ms |
16736 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
2 ms |
14684 KB |
Output is correct |
18 |
Correct |
2 ms |
14684 KB |
Output is correct |
19 |
Correct |
2 ms |
16732 KB |
Output is correct |
20 |
Correct |
2 ms |
16732 KB |
Output is correct |
21 |
Correct |
2 ms |
16732 KB |
Output is correct |
22 |
Correct |
6 ms |
25436 KB |
Output is correct |
23 |
Correct |
6 ms |
25436 KB |
Output is correct |
24 |
Correct |
6 ms |
25436 KB |
Output is correct |
25 |
Correct |
6 ms |
25432 KB |
Output is correct |
26 |
Correct |
6 ms |
25436 KB |
Output is correct |
27 |
Correct |
6 ms |
25540 KB |
Output is correct |
28 |
Correct |
6 ms |
25536 KB |
Output is correct |
29 |
Correct |
4 ms |
21084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16728 KB |
Output is correct |
2 |
Correct |
3 ms |
16968 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
2 ms |
16984 KB |
Output is correct |
5 |
Correct |
2 ms |
16732 KB |
Output is correct |
6 |
Correct |
2 ms |
16988 KB |
Output is correct |
7 |
Correct |
2 ms |
16828 KB |
Output is correct |
8 |
Correct |
2 ms |
16732 KB |
Output is correct |
9 |
Correct |
2 ms |
16988 KB |
Output is correct |
10 |
Correct |
3 ms |
16988 KB |
Output is correct |
11 |
Correct |
2 ms |
16988 KB |
Output is correct |
12 |
Correct |
3 ms |
16988 KB |
Output is correct |
13 |
Correct |
1 ms |
14680 KB |
Output is correct |
14 |
Correct |
2 ms |
16732 KB |
Output is correct |
15 |
Correct |
2 ms |
16736 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
6 ms |
25436 KB |
Output is correct |
18 |
Correct |
6 ms |
25436 KB |
Output is correct |
19 |
Correct |
6 ms |
25436 KB |
Output is correct |
20 |
Correct |
6 ms |
25432 KB |
Output is correct |
21 |
Correct |
6 ms |
25436 KB |
Output is correct |
22 |
Correct |
6 ms |
25540 KB |
Output is correct |
23 |
Correct |
6 ms |
25536 KB |
Output is correct |
24 |
Correct |
4 ms |
21084 KB |
Output is correct |
25 |
Correct |
2 ms |
14684 KB |
Output is correct |
26 |
Correct |
2 ms |
14684 KB |
Output is correct |
27 |
Correct |
2 ms |
16732 KB |
Output is correct |
28 |
Correct |
2 ms |
16732 KB |
Output is correct |
29 |
Correct |
2 ms |
16732 KB |
Output is correct |
30 |
Correct |
23 ms |
52708 KB |
Output is correct |
31 |
Correct |
22 ms |
52572 KB |
Output is correct |
32 |
Correct |
28 ms |
52840 KB |
Output is correct |
33 |
Correct |
17 ms |
51544 KB |
Output is correct |
34 |
Correct |
20 ms |
52384 KB |
Output is correct |
35 |
Correct |
22 ms |
52572 KB |
Output is correct |
36 |
Correct |
23 ms |
52360 KB |
Output is correct |
37 |
Correct |
22 ms |
52308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16728 KB |
Output is correct |
2 |
Correct |
3 ms |
16968 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
2 ms |
16984 KB |
Output is correct |
5 |
Correct |
2 ms |
16732 KB |
Output is correct |
6 |
Correct |
2 ms |
16988 KB |
Output is correct |
7 |
Correct |
2 ms |
16828 KB |
Output is correct |
8 |
Correct |
2 ms |
16732 KB |
Output is correct |
9 |
Correct |
2 ms |
16988 KB |
Output is correct |
10 |
Correct |
3 ms |
16988 KB |
Output is correct |
11 |
Correct |
2 ms |
16988 KB |
Output is correct |
12 |
Correct |
3 ms |
16988 KB |
Output is correct |
13 |
Correct |
1 ms |
14680 KB |
Output is correct |
14 |
Correct |
2 ms |
16732 KB |
Output is correct |
15 |
Correct |
2 ms |
16736 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
6 ms |
25436 KB |
Output is correct |
18 |
Correct |
6 ms |
25436 KB |
Output is correct |
19 |
Correct |
6 ms |
25436 KB |
Output is correct |
20 |
Correct |
6 ms |
25432 KB |
Output is correct |
21 |
Correct |
6 ms |
25436 KB |
Output is correct |
22 |
Correct |
6 ms |
25540 KB |
Output is correct |
23 |
Correct |
6 ms |
25536 KB |
Output is correct |
24 |
Correct |
4 ms |
21084 KB |
Output is correct |
25 |
Correct |
23 ms |
52708 KB |
Output is correct |
26 |
Correct |
22 ms |
52572 KB |
Output is correct |
27 |
Correct |
28 ms |
52840 KB |
Output is correct |
28 |
Correct |
17 ms |
51544 KB |
Output is correct |
29 |
Correct |
20 ms |
52384 KB |
Output is correct |
30 |
Correct |
22 ms |
52572 KB |
Output is correct |
31 |
Correct |
23 ms |
52360 KB |
Output is correct |
32 |
Correct |
22 ms |
52308 KB |
Output is correct |
33 |
Correct |
2 ms |
14684 KB |
Output is correct |
34 |
Correct |
2 ms |
14684 KB |
Output is correct |
35 |
Correct |
2 ms |
16732 KB |
Output is correct |
36 |
Correct |
2 ms |
16732 KB |
Output is correct |
37 |
Correct |
2 ms |
16732 KB |
Output is correct |
38 |
Correct |
110 ms |
112380 KB |
Output is correct |
39 |
Correct |
99 ms |
112468 KB |
Output is correct |
40 |
Correct |
99 ms |
112980 KB |
Output is correct |
41 |
Correct |
89 ms |
112504 KB |
Output is correct |
42 |
Correct |
287 ms |
143696 KB |
Output is correct |
43 |
Correct |
274 ms |
142928 KB |
Output is correct |
44 |
Correct |
278 ms |
143420 KB |
Output is correct |
45 |
Correct |
251 ms |
137464 KB |
Output is correct |
46 |
Correct |
147 ms |
122548 KB |
Output is correct |
47 |
Correct |
173 ms |
127480 KB |
Output is correct |
48 |
Correct |
243 ms |
140624 KB |
Output is correct |
49 |
Correct |
250 ms |
142420 KB |
Output is correct |
50 |
Correct |
136 ms |
104360 KB |
Output is correct |
51 |
Correct |
121 ms |
97796 KB |
Output is correct |
52 |
Correct |
229 ms |
136352 KB |
Output is correct |
53 |
Correct |
239 ms |
137556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
126016 KB |
Output is correct |
2 |
Correct |
41 ms |
110932 KB |
Output is correct |
3 |
Correct |
49 ms |
126084 KB |
Output is correct |
4 |
Correct |
2 ms |
14680 KB |
Output is correct |
5 |
Correct |
50 ms |
125188 KB |
Output is correct |
6 |
Correct |
49 ms |
125348 KB |
Output is correct |
7 |
Correct |
50 ms |
125124 KB |
Output is correct |
8 |
Correct |
55 ms |
125264 KB |
Output is correct |
9 |
Correct |
52 ms |
126036 KB |
Output is correct |
10 |
Correct |
53 ms |
125012 KB |
Output is correct |
11 |
Correct |
56 ms |
125016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
14684 KB |
Output is correct |
2 |
Correct |
2 ms |
14684 KB |
Output is correct |
3 |
Correct |
2 ms |
16732 KB |
Output is correct |
4 |
Correct |
2 ms |
16732 KB |
Output is correct |
5 |
Correct |
2 ms |
16732 KB |
Output is correct |
6 |
Correct |
2 ms |
16728 KB |
Output is correct |
7 |
Correct |
839 ms |
339792 KB |
Output is correct |
8 |
Correct |
1706 ms |
590932 KB |
Output is correct |
9 |
Correct |
1752 ms |
593808 KB |
Output is correct |
10 |
Correct |
1751 ms |
592892 KB |
Output is correct |
11 |
Correct |
433 ms |
276960 KB |
Output is correct |
12 |
Correct |
761 ms |
423212 KB |
Output is correct |
13 |
Correct |
852 ms |
434864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16728 KB |
Output is correct |
2 |
Correct |
3 ms |
16968 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
2 ms |
16984 KB |
Output is correct |
5 |
Correct |
2 ms |
16732 KB |
Output is correct |
6 |
Correct |
2 ms |
16988 KB |
Output is correct |
7 |
Correct |
2 ms |
16828 KB |
Output is correct |
8 |
Correct |
2 ms |
16732 KB |
Output is correct |
9 |
Correct |
2 ms |
16988 KB |
Output is correct |
10 |
Correct |
3 ms |
16988 KB |
Output is correct |
11 |
Correct |
2 ms |
16988 KB |
Output is correct |
12 |
Correct |
3 ms |
16988 KB |
Output is correct |
13 |
Correct |
1 ms |
14680 KB |
Output is correct |
14 |
Correct |
2 ms |
16732 KB |
Output is correct |
15 |
Correct |
2 ms |
16736 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
6 ms |
25436 KB |
Output is correct |
18 |
Correct |
6 ms |
25436 KB |
Output is correct |
19 |
Correct |
6 ms |
25436 KB |
Output is correct |
20 |
Correct |
6 ms |
25432 KB |
Output is correct |
21 |
Correct |
6 ms |
25436 KB |
Output is correct |
22 |
Correct |
6 ms |
25540 KB |
Output is correct |
23 |
Correct |
6 ms |
25536 KB |
Output is correct |
24 |
Correct |
4 ms |
21084 KB |
Output is correct |
25 |
Correct |
23 ms |
52708 KB |
Output is correct |
26 |
Correct |
22 ms |
52572 KB |
Output is correct |
27 |
Correct |
28 ms |
52840 KB |
Output is correct |
28 |
Correct |
17 ms |
51544 KB |
Output is correct |
29 |
Correct |
20 ms |
52384 KB |
Output is correct |
30 |
Correct |
22 ms |
52572 KB |
Output is correct |
31 |
Correct |
23 ms |
52360 KB |
Output is correct |
32 |
Correct |
22 ms |
52308 KB |
Output is correct |
33 |
Correct |
110 ms |
112380 KB |
Output is correct |
34 |
Correct |
99 ms |
112468 KB |
Output is correct |
35 |
Correct |
99 ms |
112980 KB |
Output is correct |
36 |
Correct |
89 ms |
112504 KB |
Output is correct |
37 |
Correct |
287 ms |
143696 KB |
Output is correct |
38 |
Correct |
274 ms |
142928 KB |
Output is correct |
39 |
Correct |
278 ms |
143420 KB |
Output is correct |
40 |
Correct |
251 ms |
137464 KB |
Output is correct |
41 |
Correct |
147 ms |
122548 KB |
Output is correct |
42 |
Correct |
173 ms |
127480 KB |
Output is correct |
43 |
Correct |
243 ms |
140624 KB |
Output is correct |
44 |
Correct |
250 ms |
142420 KB |
Output is correct |
45 |
Correct |
136 ms |
104360 KB |
Output is correct |
46 |
Correct |
121 ms |
97796 KB |
Output is correct |
47 |
Correct |
229 ms |
136352 KB |
Output is correct |
48 |
Correct |
239 ms |
137556 KB |
Output is correct |
49 |
Correct |
53 ms |
126016 KB |
Output is correct |
50 |
Correct |
41 ms |
110932 KB |
Output is correct |
51 |
Correct |
49 ms |
126084 KB |
Output is correct |
52 |
Correct |
2 ms |
14680 KB |
Output is correct |
53 |
Correct |
50 ms |
125188 KB |
Output is correct |
54 |
Correct |
49 ms |
125348 KB |
Output is correct |
55 |
Correct |
50 ms |
125124 KB |
Output is correct |
56 |
Correct |
55 ms |
125264 KB |
Output is correct |
57 |
Correct |
52 ms |
126036 KB |
Output is correct |
58 |
Correct |
53 ms |
125012 KB |
Output is correct |
59 |
Correct |
56 ms |
125016 KB |
Output is correct |
60 |
Correct |
2 ms |
16728 KB |
Output is correct |
61 |
Correct |
839 ms |
339792 KB |
Output is correct |
62 |
Correct |
1706 ms |
590932 KB |
Output is correct |
63 |
Correct |
1752 ms |
593808 KB |
Output is correct |
64 |
Correct |
1751 ms |
592892 KB |
Output is correct |
65 |
Correct |
433 ms |
276960 KB |
Output is correct |
66 |
Correct |
761 ms |
423212 KB |
Output is correct |
67 |
Correct |
852 ms |
434864 KB |
Output is correct |
68 |
Correct |
2 ms |
14684 KB |
Output is correct |
69 |
Correct |
2 ms |
14684 KB |
Output is correct |
70 |
Correct |
2 ms |
16732 KB |
Output is correct |
71 |
Correct |
2 ms |
16732 KB |
Output is correct |
72 |
Correct |
2 ms |
16732 KB |
Output is correct |
73 |
Correct |
946 ms |
481540 KB |
Output is correct |
74 |
Correct |
962 ms |
481668 KB |
Output is correct |
75 |
Correct |
928 ms |
481616 KB |
Output is correct |
76 |
Correct |
933 ms |
481540 KB |
Output is correct |
77 |
Correct |
4024 ms |
873300 KB |
Output is correct |
78 |
Correct |
2009 ms |
551356 KB |
Output is correct |
79 |
Correct |
2136 ms |
610640 KB |
Output is correct |
80 |
Correct |
3311 ms |
842280 KB |
Output is correct |
81 |
Correct |
2090 ms |
567160 KB |
Output is correct |
82 |
Correct |
2778 ms |
743636 KB |
Output is correct |
83 |
Correct |
3429 ms |
868572 KB |
Output is correct |
84 |
Correct |
1756 ms |
521012 KB |
Output is correct |
85 |
Correct |
3056 ms |
809700 KB |
Output is correct |
86 |
Correct |
2855 ms |
789224 KB |
Output is correct |
87 |
Correct |
2337 ms |
603504 KB |
Output is correct |
88 |
Correct |
3760 ms |
872832 KB |
Output is correct |
89 |
Correct |
3883 ms |
873644 KB |
Output is correct |
90 |
Correct |
3846 ms |
873552 KB |
Output is correct |