| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1049381 | efedmrlr | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
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"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n, m;
struct DSU {
vector<int> p, sz;
vector<int> l, r;
vector<int> used;
int mx;
void reset(int s, int mm) {
p.assign(s + 3, -1);
sz.assign(s + 3, 0);
l.assign(s + 3, INF);
r.assign(s + 3, 0);
used.assign(s + 3, -1);
mx = mm;
}
void make_set(int x) {
p[x] = x;
sz[x] = 1;
l[x] = r[x] = x;
}
int find_set(int x) {
return p[x] == x ? x : find_set(p[x]);
}
void union_set(int x, int y) {
x = find_set(x); y = find_set(y);
if(x == y) return;
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
p[y] = x;
l[x] = min(l[x], l[y]);
r[x] = max(r[x], r[y]);
}
bool check_val(int x) {
return !(l[x] == 0 || r[x] == mx);
}
};
struct Fenwick {
vector<int> data;
int sz;
void reset(int s) {
sz = s;
data.assign(sz + 3, 0);
}
void update(int ind, int val) {
ind++;
while(ind <= sz) {
data[ind] += val;
ind += (-ind) & ind;
}
}
int getSum(int ind) {
ind++;
int ret = 0;
while(ind > 0) {
ret += data[ind];
ind -= ind & (-ind);
}
return ret;
}
int query(int l, int r) {
return getSum(r) - (l > 0 ? getSum(l - 1) : 0);
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
n = (int)a.size();
m = (int)a[0].size();
vector<vector<vector<array<int, 2> > > > rows(n, vector<vector<array<int, 2> > >(m)), cols(n, vector<vector<array<int, 2> > >(m));
REP(i, n - 1) {
if(i == 0) continue;
DSU ds;
ds.reset(m, m - 1);
vector<int> ord;
REP(j, m) ord.pb(j);
sort(all(ord), [&](int x, int y) {
return a[i][x] < a[i][y];
});
int last = -1, lind = 0;
for(int k = 0; k < ord.size(); k++) {
auto &c = ord[k];
if(a[i][c] != last) {
for(int j = lind; j < k; j++) {
if(ds.used[ds.find_set(ord[j])] == lind) {
continue;
}
ds.used[ds.find_set(ord[j])] = lind;
if(!ds.check_val(ds.find_set(ord[j]))) continue;
rows[i][ds.l[ds.find_set(ord[j])]].pb({ds.r[ds.find_set(ord[j])] - ds.l[ds.find_set(ord[j])] + 1, 0});
}
last = a[i][c];
lind = k;
}
ds.make_set(c);
if(ds.p[c + 1] != -1) ds.union_set(c, c + 1);
if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1);
}
for(int j = lind; j < ord.size(); j++) {
if(ds.used[ds.find_set(ord[j])] == lind) {
continue;
}
ds.used[ds.find_set(ord[j])] = lind;
if(!ds.check_val(ds.find_set(ord[j]))) continue;
rows[i][ds.l[ds.find_set(ord[j])]].pb({ds.r[ds.find_set(ord[j])] - ds.l[ds.find_set(ord[j])] + 1, 0});
}
}
REP(j, m - 1) {
if(j == 0) continue;
DSU ds;
ds.reset(n, n - 1);
vector<int> ord;
REP(i, n) ord.pb(i);
sort(all(ord), [&](int x, int y) {
return a[x][j] < a[y][j];
});
int last = -1, lind = 0;
for(int k = 0; k < ord.size(); k++) {
auto &c = ord[k];
if(a[c][j] != last) {
for(int i = lind; i < k; i++) {
if(ds.used[ds.find_set(ord[i])] == lind) {
continue;
}
ds.used[ds.find_set(ord[i])] = lind;
if(!ds.check_val(ds.find_set(ord[i]))) continue;
cols[ds.l[ds.find_set(ord[i])]][j].pb({ds.r[ds.find_set(ord[i])] - ds.l[ds.find_set(ord[i])] + 1, 0});
}
last = a[c][j];
lind = k;
}
ds.make_set(c);
if(ds.p[c + 1] != -1) ds.union_set(c, c + 1);
if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1);
}
for(int i = lind; i < ord.size(); i++) {
if(ds.used[ds.find_set(ord[i])] == lind) {
continue;
}
ds.used[ds.find_set(ord[i])] = lind;
if(!ds.check_val(ds.find_set(ord[i]))) continue;
cols[ds.l[ds.find_set(ord[i])]][j].pb({ds.r[ds.find_set(ord[i])] - ds.l[ds.find_set(ord[i])] + 1, 0});
}
}
// cout << "rows: \n";
// for(int i = 0; i < n; i++) {
// cout << "i:" << i << "\n";
// for(auto c : row[i]) {
// cout << c[0] << " " << c[1] << "\n";
// }
// }
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
sort(all(rows[i][j]));
sort(all(cols[i][j]));
}
}
for(int i = n - 1; i >= 0; i--) {
for(int j = m - 1; j >= 0; j--) {
// cout << "i:" << i << " j:" << j << "\n";
// cout << "rows: \n";
for(auto &c : rows[i][j]) {
c[1] = 1;
if(i == n - 1) continue;
auto x = lower_bound(all(rows[i + 1][j]), c);
if(x == rows[i + 1][j].end() || (*x)[0] != c[0]) {
continue;
}
c[1] = (*x)[1] + 1;
// cout << c[0] << " " << c[1] << "\n";
}
// cout << "cols: \n";
for(auto &c : cols[i][j]) {
c[1] = 1;
if(j == m - 1) continue;
auto x = lower_bound(all(cols[i][j + 1]), c);
if(x == cols[i][j + 1].end() || (*x)[0] != c[0]) {
continue;
}
c[1] = (*x)[1] + 1;
// cout << c[0] << " " << c[1] << "\n";
}
}
}
// cout << "zort" << endl;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
sort(all(rows[i][j]), [&](array<int, 2> x, array<int, 2> y) {
return x[1] < y[1];
});
}
}
Fenwick st;
st.reset(max(n, m) + 2);
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
int id = 0;
for(auto c: rows[i][j]) {
while(id < cols[i][j].size() && cols[i][j][id][0] <= c[1]) {
st.update(cols[i][j][id][1], 1);
id++;
}
ans += st.query(c[0], max(n, m));
}
while(id > 0) {
id--;
st.update(cols[i][j][id][1], -1);
}
}
}
return ans;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int> > grid(n,vector<int>(m));
REP(i, n) REP(j, m) {
cin >> grid[i][j];
}
cout << count_rectangles(grid) << "\n";
return 0;
}