This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef int64_t lld;
typedef pair<int, int> pii;
/*
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T, typename comp = greater<T>>
using OST = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
*/
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
return out << "(" << p.ff << ", " << p.ss << ")";
}
vector<pii> tmp;
vector<vector<int>> U, D, L, R, t, ans, ansb;
vector<int> dsu;
void init(){ iota(all(dsu), 0); }
int root(int i){ return dsu[i] == i? i: dsu[i] = root(dsu[i]); }
void join(int i, int j){ dsu[root(i)] = root(j); }
struct node{
node *L, *R;
int l, r;
vector<vector<pair<int, pii>>> queries;
node(int ll, int rr, int m){
queries.resize(m);
l = ll, r = rr;
if(l != r)L = new node(l, l+r>>1, m), R = new node((l+r>>1)+1, r, m);
}
void add(int ll, int rr, int l2, int r2, int x, int y){
if(ll > r || rr < l)return;
if(ll <= l && r <= rr)queries[r2].pb({l2, {x, y}});
else L->add(ll, rr, l2, r2, x, y), R->add(ll, rr, l2, r2, x, y);
}
void answer(const vector<int>& v, function<bool(int, int)> cmp){
init(); tmp.resize(0);
for(int i = 0; i < v.size(); i++){
while(tmp.size() && cmp(v[i], tmp.back().ff))join(tmp.back().ss, i), tmp.pop_back();
tmp.pb({v[i], i});
for(auto p: queries[i]) //
if(ans[p.ss.ff][p.ss.ss] == -2 || cmp(v[root(p.ff)], ans[p.ss.ff][p.ss.ss]))
ans[p.ss.ff][p.ss.ss] = v[root(p.ff)];
}
}
void process(vector<vector<int>>& v, function<bool(int, int)> cmp){
//cout << "process" << l << " " << r << endl;
if(l != r){
L->process(v, cmp), R->process(v, cmp);
for(int i = 0; i < v[l].size(); i++)
v[l][i] = cmp(v[l][i], v[(l+r>>1)+1][i])?v[l][i]:v[(l+r>>1)+1][i];
}
answer(v[l], cmp);
//cout << "end_process" << l << " " << r << endl;
}
} *rt;
set<tuple<int, int, int, int>> st;
long long count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
ans.resize(n); for(auto& i: ans)i.resize(m);
ansb.resize(n); for(auto& i: ansb)i.resize(m, -2);
dsu.resize(m);
U = D = L = R = a;
for(int i = 1; i < n; i++){
tmp.resize(0); tmp.pb({INT_MAX, -1});
for(int j = 0; j < m; j++){
while(tmp.back().ff <= a[i][j])tmp.pop_back();
L[i][j] = tmp.back().ss;
tmp.pb({a[i][j], j});
}
tmp.resize(0); tmp.pb({INT_MAX, m});
for(int j = m-1; j > 0; j--){
while(tmp.back().ff <= a[i][j])tmp.pop_back();
R[i][j] = tmp.back().ss;
tmp.pb({a[i][j], j});
}
}
for(int j = 1; j < m; j++){
tmp.resize(0); tmp.pb({INT_MAX, -1});
for(int i = 0; i < n; i++){
while(tmp.back().ff <= a[i][j])tmp.pop_back();
U[i][j] = tmp.back().ss;
tmp.pb({a[i][j], i});
}
tmp.resize(0); tmp.pb({INT_MAX, n});
for(int i = n-1; i > 0; i--){
while(tmp.back().ff <= a[i][j])tmp.pop_back();
D[i][j] = tmp.back().ss;
tmp.pb({a[i][j], i});
}
}
rt = new node(0, n-1, m);
for(int i = 1; i <= n-2; i++)
for(int j = 1; j <= m-2; j++)
if(!(U[i][j] < 0 || D[i][j] >= n || L[i][j] < 0 || R[i][j] >= m))
rt->add(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1, i, j);
for(auto& i: ans)fill(all(i), -2); t = U, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false;
for(auto& i: ans)fill(all(i), -2); t = L, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false;
for(auto& i: ans)fill(all(i), -2); t = D, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false;
for(auto& i: ans)fill(all(i), -2); t = R, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false;
//cout << "hi" << endl;
//u.init(n, m), d.init(n, m), l.init(n, m), r.init(n, m);
for(int i = 1; i <= n-2; i++)
for(int j = 1; j <= m-2; j++)
if(ansb[i][j])
st.insert({U[i][j], L[i][j], D[i][j], R[i][j]});
return st.size();
}
Compilation message (stderr)
rect.cpp: In constructor 'node::node(int, int, int)':
rect.cpp:36:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | if(l != r)L = new node(l, l+r>>1, m), R = new node((l+r>>1)+1, r, m);
| ~^~
rect.cpp:36:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | if(l != r)L = new node(l, l+r>>1, m), R = new node((l+r>>1)+1, r, m);
| ~^~
rect.cpp: In member function 'void node::answer(const std::vector<int>&, std::function<bool(int, int)>)':
rect.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
rect.cpp: In member function 'void node::process(std::vector<std::vector<int> >&, std::function<bool(int, int)>)':
rect.cpp:57:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0; i < v[l].size(); i++)
| ~~^~~~~~~~~~~~~
rect.cpp:58:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | v[l][i] = cmp(v[l][i], v[(l+r>>1)+1][i])?v[l][i]:v[(l+r>>1)+1][i];
| ~^~
rect.cpp:58:58: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | v[l][i] = cmp(v[l][i], v[(l+r>>1)+1][i])?v[l][i]:v[(l+r>>1)+1][i];
| ~^~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:105:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
105 | for(auto& i: ans)fill(all(i), -2); t = U, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false;
| ^~~
rect.cpp:105:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
105 | for(auto& i: ans)fill(all(i), -2); t = U, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false;
| ^
rect.cpp:106:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
106 | for(auto& i: ans)fill(all(i), -2); t = L, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false;
| ^~~
rect.cpp:106:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
106 | for(auto& i: ans)fill(all(i), -2); t = L, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false;
| ^
rect.cpp:107:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
107 | for(auto& i: ans)fill(all(i), -2); t = D, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false;
| ^~~
rect.cpp:107:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
107 | for(auto& i: ans)fill(all(i), -2); t = D, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false;
| ^
rect.cpp:108:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
108 | for(auto& i: ans)fill(all(i), -2); t = R, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false;
| ^~~
rect.cpp:108:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
108 | for(auto& i: ans)fill(all(i), -2); t = R, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |