| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 561368 | fcmalkcin | 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 <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=2e3+5e2+10;
//const ll maxn=50;
const ll mod=1e9+7 ;
const ll base=1e18;
/// i believe myself
/// goal 2/7
#include "rect.h"
bool dd[maxn][maxn];
vector<pair<ll,pll>> adj[maxn];
vector<pair<ll,pll>> adjq[maxn];
vector<ll> fwt[maxn][maxn];
vector<ll> vtfwt[maxn][maxn];
ll get(ll x,ll y,ll p)
{
p=lower_bound(vtfwt[x][y].begin(),vtfwt[x][y].end(),p)-vtfwt[x][y].begin()+1;
ll ans=0;
for (int i=p;i; i -= i&(-i))
ans+=fwt[x][y][i];
return ans;
}
void update1(ll x,ll y,ll p,ll diff)
{
p=lower_bound(vtfwt[x][y].begin(),vtfwt[x][y].end(),p)-vtfwt[x][y].begin()+1;
ll len=vtfwt[x][y].size();
for (int i=p+1; i<=len; i+= i&(-i))
fwt[x][y][i]-=diff;
for (int i=1; i<=len; i+= i&(-i))
fwt[x][y][i]+=diff;
}
void update(ll p,ll l,ll r,ll diff)
{
for (int t=l; t<=r; t++)
{
update1(p,t,r,diff);
}
}
long long count_rectangles(vector<vector<ll>> a)
{
ll n=a.size();
ll m=a[0].size();
if (min(n,m)<=2)
return 0;
vector<pair<pll,ll>> vt;
for (int i=1; i+1<n; i++)
{
stack<ll> st;
vector<pll> vt1;
for (int j=0; j<m; j++)
{
while (st.size()&&a[i][st.top()]<a[i][j])
st.pop();
if (st.size())
{
ll h=st.top();
if (!dd[h][j]&&h+1<j)
{
dd[h][j]=1;
vt.pb(make_pair(make_pair(h,j),i));
vt1.pb(make_pair(h,j));
}
}
st.push(j);
}
while (st.size())
st.pop();
for (int j=m-1; j>=0; j--)
{
while (st.size()&&a[i][st.top()]<a[i][j])
st.pop();
if (st.size())
{
ll h=st.top();
if (!dd[j][h]&&j+1<h)
{
dd[j][h]=1;
vt.pb(make_pair(make_pair(j,h),i));
vt1.pb(make_pair(j,h));
}
}
st.push(j);
}
for (auto p:vt1)
dd[p.ff][p.ss]=false;
}
sort(vt.begin(),vt.end());
for (int i=0; i<vt.size(); i++)
{
ll j=i+1;
while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
j++;
j--;
auto p=vt[j].ff;
p.ff++;
p.ss--;
ll l=vt[i].ss-1;
ll r=vt[j].ss+1;
adj[l].pb(make_pair(r,p));
for (int t=l;t<=r;t++)
{
vtwft[t][p.ff].pb(p.ss);
}
i=j;
}
vt.clear();
for (int j=0; j<m; j++)
{
stack<ll> st;
vector<pll> vt1;
for (int i=0; i<n; i++)
{
while (st.size()&&a[st.top()][j]<a[i][j])
st.pop();
if (st.size())
{
ll h=st.top();
if (!dd[h][i]&&h+1<i)
{
dd[h][i]=1;
vt.pb(make_pair(make_pair(h,i),j));
vt1.pb(make_pair(h,i));
}
}
st.push(i);
}
while (st.size())
st.pop();
for (int i=n-1; i>=0; i--)
{
while (st.size()&&a[st.top()][j]<a[i][j])
st.pop();
if (st.size())
{
ll h=st.top();
if (!dd[i][h]&&i+1<h)
{
dd[i][h]=1;
vt.pb(make_pair(make_pair(i,h),j));
vt1.pb(make_pair(i,h));
}
}
st.push(i);
}
for (auto p:vt1)
dd[p.ff][p.ss]=false;
}
sort(vt.begin(),vt.end());
for (int i=0; i<vt.size(); i++)
{
ll j=i+1;
while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
j++;
j--;
ll l=vt[i].ss;
ll r=vt[j].ss;
auto p=vt[j].ff;
for (int t=l; t<=r; t++)
{
ll idnw=p.ss;
vtfwt[idnw][t].pb(r);
}
i=j;
}
for (int i=0; i<n; i++)
{
for (int j=0; j<m; j++)
{
if (vtfwt[i][j].size())
{
sort(vtfwt[i][j].begin(),vtfwt[i][j].end());
vtfwt[i][j].resize(unique(vtfwt[i][j].begin(),vtfwt[i][j].end())-vtfwt[i][j].begin());
ll len=vtfwt[i][j].size();
fwt[i][j]=vector<ll> (len+3,0);
}
}
}
for (int i=0; i<vt.size(); i++)
{
ll j=i+1;
while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
j++;
j--;
ll l=vt[i].ss;
ll r=vt[j].ss;
auto p=vt[j].ff;
update(p.ss,l,r,1);
adjq[p.ff+1].pb(make_pair(p.ss,make_pair(l,r)));
i=j;
}
long long ans=0;
for (int i=0; i<n; i++)
{
for (auto p:adjq[i])
{
update(p.ff,p.ss.ff,p.ss.ss,-1);
}
for (auto to:adj[i])
{
ll r=to.ff;
auto p=to.ss;
for (int t=i;t<=r;t++)
{
ans+=get(t,p.ff,p.ss);
}
}
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("test.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
vector<vector<ll>> a;
ll n, m;
cin>> n>> m;
for (int i=0;i<n;i++)
{
vector<ll> vt;
for (int j=0;j<m;j++)
{
ll x;
cin>> x;
vt.pb(x);
}
a.pb(vt);
}
cout <<count_rectangles(a)<<endl;
}*/
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/