/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )
/▄/ /█/ /◐/ /▐/ /▌/ /▀/ /░/ / / choose your own style!
***IT'S OUR LONG WAY TO THE OIILLLL***
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀ ░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀ ░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/
//#pragma GCC target("avx2")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container) {for (auto &u : container)os << u << " ";return os;} template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) {return os << p.first << " " << p.second;}template <class T> ostream &operator<<(ostream &os, set<T> const& con) { for (auto &u : con) os << u << " ";return os;} void pr() {} template <typename T, typename... args> void pr(T x, args... tail) {cout << x << " ";pr(tail...);}} using namespace fastio;
#define pb push_back
#define ll long long
//#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define uint unsigned int
//#define int long long
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};
//const ld pi = acos(-1.0);
const int N = 2500 + 5;
const int M = 1e9 + 7;
unordered_set < int > g[N][N], v[N][N];
ll count_rectangles(vector < vector < int > > a){
int n = a.size();
int m = a[0].size();
for (int i = 0; i < n; ++i){
vector < pii > v;
for (int j = 0; j < m; ++j){
while(v.size() && a[i][j] >= v.back().F){
if (v.size() > 1 && a[i][j] != v.back().F)
g[i][j].insert(v[v.size() - 2].S);
v.pop_back();
}
v.pb({a[i][j], j});
}
}
for (int j = 0; j < m; ++j){
vector < pii > V;
for (int i = 0; i < n; ++i){
// cout << i _ j <<": "<< V << endl;
while(V.size() && a[i][j] >= V.back().F){
if (V.size() > 1 && a[i][j] != V.back().F)
v[i][j].insert(V[V.size() - 2].S);
V.pop_back();
}
V.pb({a[i][j], i});
}
}
int ans = 0;
for (int i = 1; i < n; ++i)
for (int j = 1; j < m; ++j){
// cout << i _ j << " ";
// for (int k : v[i + 1][j]) cout << k << " ";
// cout << " : ";
// for (int k : g[i][j + 1]) cout << k << " ";
// cout<<endl;
for (int I : v[i + 1][j]){
for (int J : g[i][j + 1]){
// cout << I _ J << " ";
bool good = 1;
for (int j1 = J + 1; j1 <= j; ++j1)
if (!v[i + 1][j1].count(I)){
good = 0;
break;
}
for (int i1 = I + 1; i1 <= i; ++i1)
if (!g[i1][j + 1].count(J)){
good = 0;
break;
}
// cout << good << endl;
ans += good;
// cout<<(i - I - 1) * (j - J - 1)<<endl;
}
}
}
return ans;
}
#ifdef Estb_probitie
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n, m;
cin >> n >> m;
vector < vector < int > > a(n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j){
int x;
cin >> x;
a[i].pb(x);
}
cout << count_rectangles(a);
}
#endif // Estb_probitie
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
496 ms |
687992 KB |
Output is correct |
2 |
Correct |
498 ms |
688120 KB |
Output is correct |
3 |
Correct |
507 ms |
688120 KB |
Output is correct |
4 |
Correct |
490 ms |
688024 KB |
Output is correct |
5 |
Correct |
506 ms |
687988 KB |
Output is correct |
6 |
Correct |
496 ms |
688120 KB |
Output is correct |
7 |
Correct |
501 ms |
688060 KB |
Output is correct |
8 |
Correct |
507 ms |
687992 KB |
Output is correct |
9 |
Correct |
489 ms |
688000 KB |
Output is correct |
10 |
Correct |
501 ms |
688032 KB |
Output is correct |
11 |
Correct |
495 ms |
688100 KB |
Output is correct |
12 |
Correct |
537 ms |
688012 KB |
Output is correct |
13 |
Correct |
503 ms |
687992 KB |
Output is correct |
14 |
Correct |
492 ms |
687992 KB |
Output is correct |
15 |
Correct |
493 ms |
687992 KB |
Output is correct |
16 |
Correct |
486 ms |
687992 KB |
Output is correct |
17 |
Correct |
496 ms |
687980 KB |
Output is correct |
18 |
Correct |
498 ms |
687932 KB |
Output is correct |
19 |
Correct |
502 ms |
688024 KB |
Output is correct |
20 |
Correct |
487 ms |
687928 KB |
Output is correct |
21 |
Correct |
487 ms |
688076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
496 ms |
687992 KB |
Output is correct |
2 |
Correct |
498 ms |
688120 KB |
Output is correct |
3 |
Correct |
507 ms |
688120 KB |
Output is correct |
4 |
Correct |
490 ms |
688024 KB |
Output is correct |
5 |
Correct |
506 ms |
687988 KB |
Output is correct |
6 |
Correct |
496 ms |
688120 KB |
Output is correct |
7 |
Correct |
501 ms |
688060 KB |
Output is correct |
8 |
Correct |
507 ms |
687992 KB |
Output is correct |
9 |
Correct |
489 ms |
688000 KB |
Output is correct |
10 |
Correct |
501 ms |
688032 KB |
Output is correct |
11 |
Correct |
495 ms |
688100 KB |
Output is correct |
12 |
Correct |
537 ms |
688012 KB |
Output is correct |
13 |
Correct |
503 ms |
687992 KB |
Output is correct |
14 |
Correct |
492 ms |
687992 KB |
Output is correct |
15 |
Correct |
493 ms |
687992 KB |
Output is correct |
16 |
Correct |
486 ms |
687992 KB |
Output is correct |
17 |
Correct |
511 ms |
688584 KB |
Output is correct |
18 |
Correct |
500 ms |
688632 KB |
Output is correct |
19 |
Correct |
495 ms |
688712 KB |
Output is correct |
20 |
Correct |
505 ms |
688376 KB |
Output is correct |
21 |
Correct |
517 ms |
688720 KB |
Output is correct |
22 |
Correct |
490 ms |
688576 KB |
Output is correct |
23 |
Correct |
499 ms |
688632 KB |
Output is correct |
24 |
Correct |
484 ms |
688264 KB |
Output is correct |
25 |
Correct |
496 ms |
687980 KB |
Output is correct |
26 |
Correct |
498 ms |
687932 KB |
Output is correct |
27 |
Correct |
502 ms |
688024 KB |
Output is correct |
28 |
Correct |
487 ms |
687928 KB |
Output is correct |
29 |
Correct |
487 ms |
688076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
496 ms |
687992 KB |
Output is correct |
2 |
Correct |
498 ms |
688120 KB |
Output is correct |
3 |
Correct |
507 ms |
688120 KB |
Output is correct |
4 |
Correct |
490 ms |
688024 KB |
Output is correct |
5 |
Correct |
506 ms |
687988 KB |
Output is correct |
6 |
Correct |
496 ms |
688120 KB |
Output is correct |
7 |
Correct |
501 ms |
688060 KB |
Output is correct |
8 |
Correct |
507 ms |
687992 KB |
Output is correct |
9 |
Correct |
489 ms |
688000 KB |
Output is correct |
10 |
Correct |
501 ms |
688032 KB |
Output is correct |
11 |
Correct |
495 ms |
688100 KB |
Output is correct |
12 |
Correct |
537 ms |
688012 KB |
Output is correct |
13 |
Correct |
503 ms |
687992 KB |
Output is correct |
14 |
Correct |
492 ms |
687992 KB |
Output is correct |
15 |
Correct |
493 ms |
687992 KB |
Output is correct |
16 |
Correct |
486 ms |
687992 KB |
Output is correct |
17 |
Correct |
511 ms |
688584 KB |
Output is correct |
18 |
Correct |
500 ms |
688632 KB |
Output is correct |
19 |
Correct |
495 ms |
688712 KB |
Output is correct |
20 |
Correct |
505 ms |
688376 KB |
Output is correct |
21 |
Correct |
517 ms |
688720 KB |
Output is correct |
22 |
Correct |
490 ms |
688576 KB |
Output is correct |
23 |
Correct |
499 ms |
688632 KB |
Output is correct |
24 |
Correct |
484 ms |
688264 KB |
Output is correct |
25 |
Correct |
585 ms |
691832 KB |
Output is correct |
26 |
Correct |
591 ms |
691808 KB |
Output is correct |
27 |
Correct |
587 ms |
691832 KB |
Output is correct |
28 |
Correct |
513 ms |
690168 KB |
Output is correct |
29 |
Correct |
517 ms |
692216 KB |
Output is correct |
30 |
Correct |
507 ms |
692420 KB |
Output is correct |
31 |
Correct |
526 ms |
692088 KB |
Output is correct |
32 |
Correct |
508 ms |
692088 KB |
Output is correct |
33 |
Correct |
496 ms |
687980 KB |
Output is correct |
34 |
Correct |
498 ms |
687932 KB |
Output is correct |
35 |
Correct |
502 ms |
688024 KB |
Output is correct |
36 |
Correct |
487 ms |
687928 KB |
Output is correct |
37 |
Correct |
487 ms |
688076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
496 ms |
687992 KB |
Output is correct |
2 |
Correct |
498 ms |
688120 KB |
Output is correct |
3 |
Correct |
507 ms |
688120 KB |
Output is correct |
4 |
Correct |
490 ms |
688024 KB |
Output is correct |
5 |
Correct |
506 ms |
687988 KB |
Output is correct |
6 |
Correct |
496 ms |
688120 KB |
Output is correct |
7 |
Correct |
501 ms |
688060 KB |
Output is correct |
8 |
Correct |
507 ms |
687992 KB |
Output is correct |
9 |
Correct |
489 ms |
688000 KB |
Output is correct |
10 |
Correct |
501 ms |
688032 KB |
Output is correct |
11 |
Correct |
495 ms |
688100 KB |
Output is correct |
12 |
Correct |
537 ms |
688012 KB |
Output is correct |
13 |
Correct |
503 ms |
687992 KB |
Output is correct |
14 |
Correct |
492 ms |
687992 KB |
Output is correct |
15 |
Correct |
493 ms |
687992 KB |
Output is correct |
16 |
Correct |
486 ms |
687992 KB |
Output is correct |
17 |
Correct |
511 ms |
688584 KB |
Output is correct |
18 |
Correct |
500 ms |
688632 KB |
Output is correct |
19 |
Correct |
495 ms |
688712 KB |
Output is correct |
20 |
Correct |
505 ms |
688376 KB |
Output is correct |
21 |
Correct |
517 ms |
688720 KB |
Output is correct |
22 |
Correct |
490 ms |
688576 KB |
Output is correct |
23 |
Correct |
499 ms |
688632 KB |
Output is correct |
24 |
Correct |
484 ms |
688264 KB |
Output is correct |
25 |
Correct |
585 ms |
691832 KB |
Output is correct |
26 |
Correct |
591 ms |
691808 KB |
Output is correct |
27 |
Correct |
587 ms |
691832 KB |
Output is correct |
28 |
Correct |
513 ms |
690168 KB |
Output is correct |
29 |
Correct |
517 ms |
692216 KB |
Output is correct |
30 |
Correct |
507 ms |
692420 KB |
Output is correct |
31 |
Correct |
526 ms |
692088 KB |
Output is correct |
32 |
Correct |
508 ms |
692088 KB |
Output is correct |
33 |
Correct |
2112 ms |
716028 KB |
Output is correct |
34 |
Correct |
590 ms |
720632 KB |
Output is correct |
35 |
Correct |
609 ms |
720632 KB |
Output is correct |
36 |
Correct |
614 ms |
725624 KB |
Output is correct |
37 |
Execution timed out |
5108 ms |
734968 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
522 ms |
688632 KB |
Output is correct |
2 |
Correct |
508 ms |
688504 KB |
Output is correct |
3 |
Correct |
482 ms |
687992 KB |
Output is correct |
4 |
Correct |
506 ms |
687992 KB |
Output is correct |
5 |
Correct |
486 ms |
688508 KB |
Output is correct |
6 |
Correct |
486 ms |
688504 KB |
Output is correct |
7 |
Correct |
482 ms |
688508 KB |
Output is correct |
8 |
Correct |
482 ms |
688504 KB |
Output is correct |
9 |
Correct |
497 ms |
688632 KB |
Output is correct |
10 |
Correct |
481 ms |
688120 KB |
Output is correct |
11 |
Correct |
478 ms |
688248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
483 ms |
688120 KB |
Output is correct |
2 |
Correct |
1100 ms |
799992 KB |
Output is correct |
3 |
Correct |
1986 ms |
943408 KB |
Output is correct |
4 |
Correct |
1906 ms |
944812 KB |
Output is correct |
5 |
Correct |
1909 ms |
944888 KB |
Output is correct |
6 |
Correct |
626 ms |
718200 KB |
Output is correct |
7 |
Correct |
768 ms |
745592 KB |
Output is correct |
8 |
Correct |
766 ms |
749436 KB |
Output is correct |
9 |
Correct |
496 ms |
687980 KB |
Output is correct |
10 |
Correct |
498 ms |
687932 KB |
Output is correct |
11 |
Correct |
502 ms |
688024 KB |
Output is correct |
12 |
Correct |
487 ms |
687928 KB |
Output is correct |
13 |
Correct |
487 ms |
688076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
496 ms |
687992 KB |
Output is correct |
2 |
Correct |
498 ms |
688120 KB |
Output is correct |
3 |
Correct |
507 ms |
688120 KB |
Output is correct |
4 |
Correct |
490 ms |
688024 KB |
Output is correct |
5 |
Correct |
506 ms |
687988 KB |
Output is correct |
6 |
Correct |
496 ms |
688120 KB |
Output is correct |
7 |
Correct |
501 ms |
688060 KB |
Output is correct |
8 |
Correct |
507 ms |
687992 KB |
Output is correct |
9 |
Correct |
489 ms |
688000 KB |
Output is correct |
10 |
Correct |
501 ms |
688032 KB |
Output is correct |
11 |
Correct |
495 ms |
688100 KB |
Output is correct |
12 |
Correct |
537 ms |
688012 KB |
Output is correct |
13 |
Correct |
503 ms |
687992 KB |
Output is correct |
14 |
Correct |
492 ms |
687992 KB |
Output is correct |
15 |
Correct |
493 ms |
687992 KB |
Output is correct |
16 |
Correct |
486 ms |
687992 KB |
Output is correct |
17 |
Correct |
511 ms |
688584 KB |
Output is correct |
18 |
Correct |
500 ms |
688632 KB |
Output is correct |
19 |
Correct |
495 ms |
688712 KB |
Output is correct |
20 |
Correct |
505 ms |
688376 KB |
Output is correct |
21 |
Correct |
517 ms |
688720 KB |
Output is correct |
22 |
Correct |
490 ms |
688576 KB |
Output is correct |
23 |
Correct |
499 ms |
688632 KB |
Output is correct |
24 |
Correct |
484 ms |
688264 KB |
Output is correct |
25 |
Correct |
585 ms |
691832 KB |
Output is correct |
26 |
Correct |
591 ms |
691808 KB |
Output is correct |
27 |
Correct |
587 ms |
691832 KB |
Output is correct |
28 |
Correct |
513 ms |
690168 KB |
Output is correct |
29 |
Correct |
517 ms |
692216 KB |
Output is correct |
30 |
Correct |
507 ms |
692420 KB |
Output is correct |
31 |
Correct |
526 ms |
692088 KB |
Output is correct |
32 |
Correct |
508 ms |
692088 KB |
Output is correct |
33 |
Correct |
2112 ms |
716028 KB |
Output is correct |
34 |
Correct |
590 ms |
720632 KB |
Output is correct |
35 |
Correct |
609 ms |
720632 KB |
Output is correct |
36 |
Correct |
614 ms |
725624 KB |
Output is correct |
37 |
Execution timed out |
5108 ms |
734968 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |