| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 817105 | prvocislo | 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 <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "rect.h"
typedef long long ll;
using namespace std;
ll ans = 0;
struct obdl
{
int x1, y1, x2, y2;
};
vector<obdl> make(vector<vector<int> > a)
{
int n = a.size(), m = a[0].size();
vector<set<pair<int, int> > > end(n);
for (int i = 0; i < n; i++)
{
vector<int> ri(m, m), li(m, -1);
vector<int> st;
for (int j = 0; j < m; j++) // najdeme najblizsi vacsi
{
while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
if (!st.empty() && st.back() + 1 < j) li[j] = st.back();
st.push_back(j);
}
st.clear();
for (int j = m - 1; j >= 0; j--) // najdeme najblizsi vacsi
{
while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
if (!st.empty() && st.back() - 1 > j) ri[j] = st.back();
st.push_back(j);
}
for (int j = 0; j < m; j++)
{
if (ri[j] != m && li[ri[j]] <= j) end[i].insert({ j + 1, ri[j] - 1 });
if (li[j] != -1 && ri[li[j]] >= j) end[i].insert({ li[j] + 1, j - 1 });
}
}
vector<obdl>o;
for (int i = 0; i < n; i++) for (pair<int, int> p : end[i])
{
int j = i + 1;
while (j < n && end[j].count(p)) end[j++].erase(p);
o.push_back({ i, p.first, j - 1, p.second });
}
return o;
}
const int maxn = 2505;
int st[maxn * 2];
void upd(int i, int x)
{
for (i += maxn; i > 0; i >>= 1) st[i] += x;
}
int query(int l, int r)
{
int ans = 0;
for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) ans += st[l++];
if (r & 1) ans += st[--r];
}
return ans;
}
struct udaj { int x, y, t; };
bool cmp(udaj a, udaj b)
{
if (a.x != b.x) return a.x < b.x;
return a.t > b.t;
}
ll count_rectangles(vector<vector<int> > a)
{
int n = a.size(), m = a[0].size();
vector<vector<vector<udaj> > > v(n, vector<vector<udaj> >(m));
vector<obdl> o1 = make(a);
for (obdl o : o1) for (int x = o.x1; x <= o.x2; x++) v[x][o.y1].push_back({ o.x2, o.y2, 1 });
vector<vector<int> > b(m, vector<int>(n));
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[j][i] = a[i][j];
vector<obdl> o2 = make(b);
for (obdl& i : o2) swap(i.x1, i.y1), swap(i.x2, i.y2);
for (obdl o : o2) for (int y = o.y1; y <= o.y2; y++) v[o.x1][y].push_back({ o.x2, o.y2, 2 });
ll ans = 0;
for (int x = 0; x < n; x++) for (int y = 0; y < m; y++)
{
sort(v[x][y].begin(), v[x][y].end(), cmp);
ll sum = 0;
for (udaj u : v[x][y])
{
if (u.t == 2) upd(u.y, 1);
else sum += query(u.y, maxn - 1);
}
for (udaj u : v[x][y]) if (u.t == 2) upd(u.y, -1);
ans += sum;
//cout << sum << " \n"[y == m - 1];
}
return ans;
}