#include <bits/stdc++.h>
#include <math.h>
#include <chrono>
using namespace std;
#pragma GCC optimize("-O3")
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10) //cin.tie(0); cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define all(c) (c).begin(), (c).end()
#define what(x) cerr << #x << " is " << x << endl;
const int MAXN = 2505; //UWAGA
vector<int> prawo[MAXN][MAXN];
vector<int> dol[MAXN][MAXN];
vector<pii> R[MAXN][MAXN];
vector<pii> D[MAXN][MAXN];
int n, m;
int tab[MAXN][MAXN];
long long ans = 0;
vector<pair<pii, pii>> odp;
void wypisz()
{
sort(all(odp));
for (auto a : odp)
{
cerr << a.st.st << " " << a.st.nd << " " << a.nd.st << " " << a.nd.nd << endl;
}
}
void wypelnij2prawo()
{
rep(j, m)
{
vector<pii> X(max(m, n) + 10, {-1, -1});
for (int i = n - 1; i >= 0; i--)
for (int a : prawo[i][j])
{
X[a] = (X[a].st == i + 1) ? mp(i, X[a].nd + 1) : mp(i, 1);
R[i][j].pb({a, X[a].nd}); //glebokosc i ile
}
}
}
void wypelnij2dol()
{
rep(i, n)
{
vector<pii> X(max(m, n) + 10, {-1, -1});
for (int j = m - 1; j >= 0; j--)
for (int a : dol[i][j])
{
X[a] = (X[a].st == j + 1) ? mp(j, X[a].nd + 1) : mp(j, 1);
D[i][j].pb({a, X[a].nd}); //glebokosc i ile
}
}
}
vector<vector<int>> wypelnij1(vector<int> &Q)
{
vector<pii> X;
rep(j, Q.size())
X.pb({Q[j], j});
vector<vector<int>> P(Q.size());
sort(all(X));
reverse(all(X));
set<pii> S;
int j = 0;
while (j < Q.size())
{
int k = j;
while (k + 1 < m && X[j].st == X[k + 1].st)
k++;
for (int l = j; l <= k; l++)
{
// cerr << X[l].nd << " " << X[l].st << endl;
S.insert({X[l].nd, X[l].st});
}
for (int l = j; l <= k; l++)
{
auto r = S.find({X[l].nd, X[l].st});
auto q = (r == S.begin()) ? r : next(r, -1);
auto s = (next(r, 1) == S.end()) ? r : next(r, 1);
// cerr << q->st << " " << r->st << " " << s->st << endl;
if (r->st - q->st - 1 > 0) //popraawic!!!!
{
P[q->st].pb(r->st - q->st - 1);
//cerr << q->st << " ech1 " << r->st << endl;
}
if (s->st - r->st - 1 > 0 && s->nd != r->nd)
{
P[r->st].pb(s->st - r->st - 1);
//cerr << s->st << " ech2 " << r->st << endl;
}
}
j = k + 1;
}
return P;
}
const int rozmiar = (1 << 12);
int ile[3 * rozmiar];
vector<int> zap;
void dodaj(int x)
{
x += rozmiar;
while (x > 0)
{
zap.pb(x);
ile[x]++;
x /= 2;
}
}
int get(int x)
{
int p = rozmiar;
int q = rozmiar + x;
int wynik = 0;
while (p <= q)
{
if (q % 2 == 0)
{
wynik += ile[q];
q--;
}
p /= 2;
q /= 2;
}
//what(wynik);
return wynik;
}
void clear()
{
for (int a : zap)
ile[a] = 0;
zap.clear();
}
void solve(int i, int j)
{
//s cerr << i << " " << j << endl;
if (R[i + 1][j].size() == 0 || D[i][j + 1].size() == 0)
return;
for (auto &B : D[i][j + 1])
swap(B.st, B.nd);
sort(all(R[i + 1][j]), greater<pii>());
sort(all(D[i][j + 1]), greater<pii>());
/*
cerr << "obecne tutaj::" << endl;
for (auto A : D[i][j + 1])
cerr << A.st << " " << A.nd << endl;
cerr << endl;
for (auto A : R[i + 1][j])
cerr << A.st << " " << A.nd << endl;
cerr << "koniec" << endl;
*/
int k = 0;
int l = 0;
while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
{
if (l == R[i + 1][j].size())
{
dodaj(D[i][j + 1][k].nd);
k++;
continue;
}
if (k == D[i][j + 1].size())
{
ans += get(R[i + 1][j][l].nd);
l++;
continue;
}
if (R[i + 1][j][l].st <= D[i][j + 1][k].st)
{
dodaj(D[i][j + 1][k].nd);
k++;
continue;
}
else
{
ans += get(R[i + 1][j][l].nd);
l++;
continue;
}
}
clear();
}
long long count_rectangles(vector<vector<int32_t>> A)
{
n = A.size();
m = A[0].size();
rep(i, n) rep(j, m) tab[i][j] = A[i][j];
rep(i, n)
{
auto X = wypelnij1(A[i]);
rep(j, m)
prawo[i][j] = X[j];
}
rep(j, m)
{
vector<int> Y;
rep(i, n)
Y.pb(tab[i][j]);
auto X = wypelnij1(Y);
rep(i, n)
dol[i][j] = X[i];
}
wypelnij2prawo();
wypelnij2dol();
/*
cerr << "DOL" << endl;
rep(i, n)
{
rep(j, m)
{
cerr << i << " " << j << ":: ";
for (auto a : D[i][j])
cerr << a.st << " " << a.nd << ", ";
cerr << endl;
// cout << a << " /// ";
}
cerr << endl;
}
cerr << "PRAWO" << endl;
rep(i, n)
{
rep(j, m)
{
cerr << i << " " << j << ":: ";
for (auto a : R[i][j])
cerr << a.st << " " << a.nd << ", ";
// cout << a << " /// ";
cerr << endl;
}
cerr << endl;
}
*/
rep(i, n - 1) rep(j, m - 1) solve(i, j);
return ans;
}
/*
main()
{
_upgrade;
string S;
cin >> S;
int a, b;
cin >> a >> b;
vector<vector<int>> X(a, vector<int>(b));
rep(i, a) rep(j, b) cin >> X[i][j];
cout << count_rectangles(X)
<< endl;
// wypisz();
}
*/
Compilation message
rect.cpp: In function 'std::vector<std::vector<int> > wypelnij1(std::vector<int>&)':
rect.cpp:15:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i = 0; i < (n); ++i)
^
rect.cpp:72:5: note: in expansion of macro 'rep'
rep(j, Q.size())
^~~
rect.cpp:79:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < Q.size())
~~^~~~~~~~~~
rect.cpp: In function 'void solve(int, int)':
rect.cpp:175:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:175:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:178:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l == R[i + 1][j].size())
~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:184:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k == D[i][j + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
528 ms |
589852 KB |
Output is correct |
2 |
Correct |
534 ms |
590116 KB |
Output is correct |
3 |
Correct |
531 ms |
589944 KB |
Output is correct |
4 |
Correct |
532 ms |
590044 KB |
Output is correct |
5 |
Correct |
539 ms |
589904 KB |
Output is correct |
6 |
Correct |
569 ms |
589936 KB |
Output is correct |
7 |
Correct |
592 ms |
590016 KB |
Output is correct |
8 |
Correct |
550 ms |
589944 KB |
Output is correct |
9 |
Correct |
532 ms |
589944 KB |
Output is correct |
10 |
Correct |
533 ms |
589984 KB |
Output is correct |
11 |
Correct |
546 ms |
589952 KB |
Output is correct |
12 |
Correct |
535 ms |
589944 KB |
Output is correct |
13 |
Correct |
532 ms |
589816 KB |
Output is correct |
14 |
Correct |
539 ms |
589816 KB |
Output is correct |
15 |
Correct |
536 ms |
589816 KB |
Output is correct |
16 |
Correct |
535 ms |
589764 KB |
Output is correct |
17 |
Correct |
541 ms |
589684 KB |
Output is correct |
18 |
Correct |
574 ms |
589776 KB |
Output is correct |
19 |
Correct |
551 ms |
590084 KB |
Output is correct |
20 |
Correct |
538 ms |
589996 KB |
Output is correct |
21 |
Correct |
537 ms |
589756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
528 ms |
589852 KB |
Output is correct |
2 |
Correct |
534 ms |
590116 KB |
Output is correct |
3 |
Correct |
531 ms |
589944 KB |
Output is correct |
4 |
Correct |
532 ms |
590044 KB |
Output is correct |
5 |
Correct |
539 ms |
589904 KB |
Output is correct |
6 |
Correct |
569 ms |
589936 KB |
Output is correct |
7 |
Correct |
592 ms |
590016 KB |
Output is correct |
8 |
Correct |
550 ms |
589944 KB |
Output is correct |
9 |
Correct |
532 ms |
589944 KB |
Output is correct |
10 |
Correct |
533 ms |
589984 KB |
Output is correct |
11 |
Correct |
546 ms |
589952 KB |
Output is correct |
12 |
Correct |
535 ms |
589944 KB |
Output is correct |
13 |
Correct |
532 ms |
589816 KB |
Output is correct |
14 |
Correct |
539 ms |
589816 KB |
Output is correct |
15 |
Correct |
536 ms |
589816 KB |
Output is correct |
16 |
Correct |
535 ms |
589764 KB |
Output is correct |
17 |
Correct |
556 ms |
591056 KB |
Output is correct |
18 |
Correct |
553 ms |
591040 KB |
Output is correct |
19 |
Correct |
540 ms |
591072 KB |
Output is correct |
20 |
Correct |
541 ms |
590436 KB |
Output is correct |
21 |
Correct |
560 ms |
590672 KB |
Output is correct |
22 |
Correct |
546 ms |
590744 KB |
Output is correct |
23 |
Correct |
554 ms |
590840 KB |
Output is correct |
24 |
Correct |
552 ms |
590456 KB |
Output is correct |
25 |
Correct |
541 ms |
589684 KB |
Output is correct |
26 |
Correct |
574 ms |
589776 KB |
Output is correct |
27 |
Correct |
551 ms |
590084 KB |
Output is correct |
28 |
Correct |
538 ms |
589996 KB |
Output is correct |
29 |
Correct |
537 ms |
589756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
528 ms |
589852 KB |
Output is correct |
2 |
Correct |
534 ms |
590116 KB |
Output is correct |
3 |
Correct |
531 ms |
589944 KB |
Output is correct |
4 |
Correct |
532 ms |
590044 KB |
Output is correct |
5 |
Correct |
539 ms |
589904 KB |
Output is correct |
6 |
Correct |
569 ms |
589936 KB |
Output is correct |
7 |
Correct |
592 ms |
590016 KB |
Output is correct |
8 |
Correct |
550 ms |
589944 KB |
Output is correct |
9 |
Correct |
532 ms |
589944 KB |
Output is correct |
10 |
Correct |
533 ms |
589984 KB |
Output is correct |
11 |
Correct |
546 ms |
589952 KB |
Output is correct |
12 |
Correct |
535 ms |
589944 KB |
Output is correct |
13 |
Correct |
532 ms |
589816 KB |
Output is correct |
14 |
Correct |
539 ms |
589816 KB |
Output is correct |
15 |
Correct |
536 ms |
589816 KB |
Output is correct |
16 |
Correct |
535 ms |
589764 KB |
Output is correct |
17 |
Correct |
556 ms |
591056 KB |
Output is correct |
18 |
Correct |
553 ms |
591040 KB |
Output is correct |
19 |
Correct |
540 ms |
591072 KB |
Output is correct |
20 |
Correct |
541 ms |
590436 KB |
Output is correct |
21 |
Correct |
560 ms |
590672 KB |
Output is correct |
22 |
Correct |
546 ms |
590744 KB |
Output is correct |
23 |
Correct |
554 ms |
590840 KB |
Output is correct |
24 |
Correct |
552 ms |
590456 KB |
Output is correct |
25 |
Correct |
590 ms |
596324 KB |
Output is correct |
26 |
Correct |
582 ms |
596232 KB |
Output is correct |
27 |
Correct |
587 ms |
596588 KB |
Output is correct |
28 |
Correct |
581 ms |
592888 KB |
Output is correct |
29 |
Correct |
599 ms |
593984 KB |
Output is correct |
30 |
Correct |
613 ms |
594040 KB |
Output is correct |
31 |
Correct |
596 ms |
594036 KB |
Output is correct |
32 |
Correct |
618 ms |
594040 KB |
Output is correct |
33 |
Correct |
541 ms |
589684 KB |
Output is correct |
34 |
Correct |
574 ms |
589776 KB |
Output is correct |
35 |
Correct |
551 ms |
590084 KB |
Output is correct |
36 |
Correct |
538 ms |
589996 KB |
Output is correct |
37 |
Correct |
537 ms |
589756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
528 ms |
589852 KB |
Output is correct |
2 |
Correct |
534 ms |
590116 KB |
Output is correct |
3 |
Correct |
531 ms |
589944 KB |
Output is correct |
4 |
Correct |
532 ms |
590044 KB |
Output is correct |
5 |
Correct |
539 ms |
589904 KB |
Output is correct |
6 |
Correct |
569 ms |
589936 KB |
Output is correct |
7 |
Correct |
592 ms |
590016 KB |
Output is correct |
8 |
Correct |
550 ms |
589944 KB |
Output is correct |
9 |
Correct |
532 ms |
589944 KB |
Output is correct |
10 |
Correct |
533 ms |
589984 KB |
Output is correct |
11 |
Correct |
546 ms |
589952 KB |
Output is correct |
12 |
Correct |
535 ms |
589944 KB |
Output is correct |
13 |
Correct |
532 ms |
589816 KB |
Output is correct |
14 |
Correct |
539 ms |
589816 KB |
Output is correct |
15 |
Correct |
536 ms |
589816 KB |
Output is correct |
16 |
Correct |
535 ms |
589764 KB |
Output is correct |
17 |
Correct |
556 ms |
591056 KB |
Output is correct |
18 |
Correct |
553 ms |
591040 KB |
Output is correct |
19 |
Correct |
540 ms |
591072 KB |
Output is correct |
20 |
Correct |
541 ms |
590436 KB |
Output is correct |
21 |
Correct |
560 ms |
590672 KB |
Output is correct |
22 |
Correct |
546 ms |
590744 KB |
Output is correct |
23 |
Correct |
554 ms |
590840 KB |
Output is correct |
24 |
Correct |
552 ms |
590456 KB |
Output is correct |
25 |
Correct |
590 ms |
596324 KB |
Output is correct |
26 |
Correct |
582 ms |
596232 KB |
Output is correct |
27 |
Correct |
587 ms |
596588 KB |
Output is correct |
28 |
Correct |
581 ms |
592888 KB |
Output is correct |
29 |
Correct |
599 ms |
593984 KB |
Output is correct |
30 |
Correct |
613 ms |
594040 KB |
Output is correct |
31 |
Correct |
596 ms |
594036 KB |
Output is correct |
32 |
Correct |
618 ms |
594040 KB |
Output is correct |
33 |
Correct |
1028 ms |
632204 KB |
Output is correct |
34 |
Correct |
980 ms |
620604 KB |
Output is correct |
35 |
Correct |
943 ms |
620760 KB |
Output is correct |
36 |
Correct |
865 ms |
609292 KB |
Output is correct |
37 |
Correct |
1257 ms |
662864 KB |
Output is correct |
38 |
Correct |
1249 ms |
662760 KB |
Output is correct |
39 |
Correct |
1267 ms |
663352 KB |
Output is correct |
40 |
Correct |
1366 ms |
658592 KB |
Output is correct |
41 |
Correct |
978 ms |
614608 KB |
Output is correct |
42 |
Correct |
1069 ms |
619872 KB |
Output is correct |
43 |
Correct |
1303 ms |
633520 KB |
Output is correct |
44 |
Correct |
1295 ms |
635640 KB |
Output is correct |
45 |
Correct |
941 ms |
614276 KB |
Output is correct |
46 |
Correct |
902 ms |
612576 KB |
Output is correct |
47 |
Correct |
1255 ms |
632076 KB |
Output is correct |
48 |
Correct |
1267 ms |
633012 KB |
Output is correct |
49 |
Correct |
541 ms |
589684 KB |
Output is correct |
50 |
Correct |
574 ms |
589776 KB |
Output is correct |
51 |
Correct |
551 ms |
590084 KB |
Output is correct |
52 |
Correct |
538 ms |
589996 KB |
Output is correct |
53 |
Correct |
537 ms |
589756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
576 ms |
590652 KB |
Output is correct |
2 |
Correct |
544 ms |
590428 KB |
Output is correct |
3 |
Correct |
546 ms |
590072 KB |
Output is correct |
4 |
Correct |
540 ms |
589788 KB |
Output is correct |
5 |
Correct |
549 ms |
590456 KB |
Output is correct |
6 |
Correct |
596 ms |
590324 KB |
Output is correct |
7 |
Correct |
623 ms |
590328 KB |
Output is correct |
8 |
Correct |
553 ms |
590180 KB |
Output is correct |
9 |
Correct |
633 ms |
590304 KB |
Output is correct |
10 |
Correct |
575 ms |
590072 KB |
Output is correct |
11 |
Correct |
621 ms |
590204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
547 ms |
589868 KB |
Output is correct |
2 |
Correct |
3251 ms |
719704 KB |
Output is correct |
3 |
Execution timed out |
5123 ms |
760728 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
528 ms |
589852 KB |
Output is correct |
2 |
Correct |
534 ms |
590116 KB |
Output is correct |
3 |
Correct |
531 ms |
589944 KB |
Output is correct |
4 |
Correct |
532 ms |
590044 KB |
Output is correct |
5 |
Correct |
539 ms |
589904 KB |
Output is correct |
6 |
Correct |
569 ms |
589936 KB |
Output is correct |
7 |
Correct |
592 ms |
590016 KB |
Output is correct |
8 |
Correct |
550 ms |
589944 KB |
Output is correct |
9 |
Correct |
532 ms |
589944 KB |
Output is correct |
10 |
Correct |
533 ms |
589984 KB |
Output is correct |
11 |
Correct |
546 ms |
589952 KB |
Output is correct |
12 |
Correct |
535 ms |
589944 KB |
Output is correct |
13 |
Correct |
532 ms |
589816 KB |
Output is correct |
14 |
Correct |
539 ms |
589816 KB |
Output is correct |
15 |
Correct |
536 ms |
589816 KB |
Output is correct |
16 |
Correct |
535 ms |
589764 KB |
Output is correct |
17 |
Correct |
556 ms |
591056 KB |
Output is correct |
18 |
Correct |
553 ms |
591040 KB |
Output is correct |
19 |
Correct |
540 ms |
591072 KB |
Output is correct |
20 |
Correct |
541 ms |
590436 KB |
Output is correct |
21 |
Correct |
560 ms |
590672 KB |
Output is correct |
22 |
Correct |
546 ms |
590744 KB |
Output is correct |
23 |
Correct |
554 ms |
590840 KB |
Output is correct |
24 |
Correct |
552 ms |
590456 KB |
Output is correct |
25 |
Correct |
590 ms |
596324 KB |
Output is correct |
26 |
Correct |
582 ms |
596232 KB |
Output is correct |
27 |
Correct |
587 ms |
596588 KB |
Output is correct |
28 |
Correct |
581 ms |
592888 KB |
Output is correct |
29 |
Correct |
599 ms |
593984 KB |
Output is correct |
30 |
Correct |
613 ms |
594040 KB |
Output is correct |
31 |
Correct |
596 ms |
594036 KB |
Output is correct |
32 |
Correct |
618 ms |
594040 KB |
Output is correct |
33 |
Correct |
1028 ms |
632204 KB |
Output is correct |
34 |
Correct |
980 ms |
620604 KB |
Output is correct |
35 |
Correct |
943 ms |
620760 KB |
Output is correct |
36 |
Correct |
865 ms |
609292 KB |
Output is correct |
37 |
Correct |
1257 ms |
662864 KB |
Output is correct |
38 |
Correct |
1249 ms |
662760 KB |
Output is correct |
39 |
Correct |
1267 ms |
663352 KB |
Output is correct |
40 |
Correct |
1366 ms |
658592 KB |
Output is correct |
41 |
Correct |
978 ms |
614608 KB |
Output is correct |
42 |
Correct |
1069 ms |
619872 KB |
Output is correct |
43 |
Correct |
1303 ms |
633520 KB |
Output is correct |
44 |
Correct |
1295 ms |
635640 KB |
Output is correct |
45 |
Correct |
941 ms |
614276 KB |
Output is correct |
46 |
Correct |
902 ms |
612576 KB |
Output is correct |
47 |
Correct |
1255 ms |
632076 KB |
Output is correct |
48 |
Correct |
1267 ms |
633012 KB |
Output is correct |
49 |
Correct |
576 ms |
590652 KB |
Output is correct |
50 |
Correct |
544 ms |
590428 KB |
Output is correct |
51 |
Correct |
546 ms |
590072 KB |
Output is correct |
52 |
Correct |
540 ms |
589788 KB |
Output is correct |
53 |
Correct |
549 ms |
590456 KB |
Output is correct |
54 |
Correct |
596 ms |
590324 KB |
Output is correct |
55 |
Correct |
623 ms |
590328 KB |
Output is correct |
56 |
Correct |
553 ms |
590180 KB |
Output is correct |
57 |
Correct |
633 ms |
590304 KB |
Output is correct |
58 |
Correct |
575 ms |
590072 KB |
Output is correct |
59 |
Correct |
621 ms |
590204 KB |
Output is correct |
60 |
Correct |
547 ms |
589868 KB |
Output is correct |
61 |
Correct |
3251 ms |
719704 KB |
Output is correct |
62 |
Execution timed out |
5123 ms |
760728 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |