| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1054865 | 2024-08-12T12:47:03 Z | mychecksedad | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KB |
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
// #define ll long long
#define pb push_back
#define ff first
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ss second
// #define int short
const int N = 2502, K = 20;
int c = 0, C[100000];
struct Fenwick{
int n;
vector<int> t, U;
Fenwick(int _n){
n = _n;
t.resize(n+1, 0);
}
void add(int v){
while(v <= n){
t[v]++;
C[c++] = v;
v += (v&-v);
}
}
int get(int v){
int res = 0;
while(v > 0){
res += t[v];
v -= (v&-v);
}
return res;
}
void rollback(){
for(int i = 0; i < c; ++i) t[C[i]] = 0;
c = 0;
}
};
vector<int> colranges[N][N];
vector<int> rowranges[N][N];
long long count_rectangles(std::vector<std::vector<int32_t> > a) {
int n = a.size();
int m = a[0].size();
if(n < 3 || m < 3){
return 0;
}
long long ans = 0;
vector<vector<int>> L, R, D, U;
L.resize(n, vector<int>(m));
R.resize(n, vector<int>(m));
D.resize(n, vector<int>(m));
U.resize(n, vector<int>(m));
for(int i = 0; i < n; ++i){
vector<int> q;
for(int j = 0; j < m; ++j){
while(!q.empty() && a[i][q.back()] <= a[i][j]) q.pop_back();
if(q.empty()){
L[i][j] = -1;
}else{
L[i][j] = q.back();
}
q.pb(j);
}
q.clear();
for(int j = m - 1; j >= 0; --j){
while(!q.empty() && a[i][q.back()] <= a[i][j]) q.pop_back();
if(q.empty()){
R[i][j] = m;
}else{
R[i][j] = q.back();
}
q.pb(j);
}
}
for(int j = 0; j < m; ++j){
vector<int> q;
for(int i = 0; i < n; ++i){
while(!q.empty() && a[q.back()][j] <= a[i][j]) q.pop_back();
if(q.empty()){
U[i][j] = -1;
}else{
U[i][j] = q.back();
}
q.pb(i);
}
q.clear();
for(int i = n - 1; i >= 0; --i){
while(!q.empty() && a[q.back()][j] <= a[i][j]) q.pop_back();
if(q.empty()){
D[i][j] = n;
}else{
D[i][j] = q.back();
}
q.pb(i);
}
}
vector<vector<vector<int>>> rangesL(n, vector<vector<int>>(m));
vector<vector<vector<int>>> rangesU(n, vector<vector<int>>(m));
for(int i = 1; i + 1 < n; ++i){
for(int j = 1; j + 1 < m; ++j){
int l = L[i][j], r = R[i][j];
while(l > -1 && r < m){
// cout << i << ' ' << j << ' ' << l + 1 << ' ' << r - 1 << '\n';
rangesL[i][r - 1].pb(l + 1);
if(a[i][l] < a[i][r]){
l = L[i][l];
}else if(a[i][l] > a[i][r]){
r = R[i][r];
}else{
l = L[i][l];
r = R[i][r];
}
}
}
}
for(int j = 1; j + 1 < m; ++j){
for(int i = 1; i + 1 < n; ++i){
int l = U[i][j], r = D[i][j];
while(l > -1 && r < n){
// cout << l << ' ' << r << ' ' << i << ' ' << j << '\n';
rangesU[r - 1][j].pb(l + 1);
if(a[l][j] < a[r][j]){
l = U[l][j];
}else if(a[l][j] > a[r][j]){
r = D[r][j];
}else{
l = U[l][j];
r = D[r][j];
}
}
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j) L[i][j].clear(), D[i][j].clear(), R[i][j].clear(), U[i][j].clear();
}
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << L[i][j] << ' ';en;
// }
// en;en;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << R[i][j] << ' ';en;
// }
// en;en;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << U[i][j] << ' ';en;
// }
// en;en;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << D[i][j] << ' ';en;
// }
// vector<vector<vector<int>>> colranges(max(n,m), vector<vector<int>>(max(n,m)));
// vector<vector<vector<int>>> rowranges(max(n,m), vector<vector<int>>(max(n,m)));
// cout << "wtf" << endl;
for(int i = 1; i + 1 < n; ++i){
Fenwick fenw(max(n,m));
for(int j = 1; j + 1 < m; ++j){
sort(all(rangesL[i][j]), greater<int>());
rangesL[i][j].erase(unique(all(rangesL[i][j])), rangesL[i][j].end());
sort(all(rangesU[i][j]), greater<int>());
rangesU[i][j].erase(unique(all(rangesU[i][j])), rangesU[i][j].end());
int ls = rangesL[i][j].size();
int us = rangesU[i][j].size();
// cout << i << ' ' << j << '\n';
// cout << "L: ";
for(int x = 0; x < ls; ++x){
if(colranges[j][rangesL[i][j][x]].size() && colranges[j][rangesL[i][j][x]].back() < i - 1){
colranges[j][rangesL[i][j][x]].clear();
}
colranges[j][rangesL[i][j][x]].pb(i);
// cout << rangesL[i][j][x] << ' ';
}
// cout << "R: ";
for(int x = 0; x < us; ++x){
if(rowranges[i][rangesU[i][j][x]].size() && rowranges[i][rangesU[i][j][x]].back() < j - 1){
rowranges[i][rangesU[i][j][x]].clear();
}
rowranges[i][rangesU[i][j][x]].pb(j);
// cout << rangesU[i][j][x] << ' ';
}
// en;en;
// Fenwick fenw();
sort(all(rangesL[i][j]), [&](const int &g, const int &h){
return colranges[j][g].size() < colranges[j][h].size();
});
// sort(all(rangesU[i][j]), [&](const int &g, const int &h){
// return rowranges[i][g].size() > rowranges[i][h].size();
// });
int p = ls - 1;
for(int y = us - 1; y >= 0; --y){
int u = rangesU[i][j][y];
// if(y < us - 1) assert(rangesU[i][j][y] >= rangesU[i][j][u + 1]);
int sz = rowranges[i][u].size();
// if(p != -1) cout << colranges[j][rangesL[i][j][p]].size() << ' ' << i - u + 1 << '\n';
while(p > -1 && colranges[j][rangesL[i][j][p]].size() >= i - u + 1){
fenw.add(j - rangesL[i][j][p] + 1);
// cout << j - rangesL[i][j][p] + 1 << 'f';
--p;
}
ans += fenw.get(sz);
// cout << sz << ' ' << i << ' ' << j << ' ' << u << ' ' << ans << '\n';
// for(int x = ls - 1; x >= 0; --x){
// int l = rangesL[i][j][x];
// cout << i << ' ' << j << ' ' << u << ' ' << l << '\n';
// cout << (rowranges[i][u].size() >= j - l + 1 && rowranges[i][u][int(rowranges[i][u].size()) - (j - l + 1)] == l) << ' ' <<
// (colranges[j][l].size() >= i - u + 1 && colranges[j][l][int(colranges[j][l].size()) - (i - u + 1)] == u) << '\n';
// if(sz >= j - l + 1
// && colranges[j][l].size() >= i - u + 1){
// ++ans;
// }
// }
}
fenw.rollback();
}
}
return ans;
}