| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 294355 | Pajaraja | 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"
#include <bits/stdc++.h>
#define MAXN 2507
using namespace std;
set<int> s[MAXN][MAXN];
vector<int> ind[MAXN];
int qx[MAXN*MAXN],qy[MAXN*MAXN],ql[MAXN*MAXN],qt[MAXN*MAXN],cnt;
stack<int> st;
int bit[MAXN][MAXN];
void upd(int k,int u,int v)
{
while(u<MAXN)
{
bit[k][u]+=v;
u+=u&(-u);
}
}
int fnd(int k,int u)
{
int sol=0;
while(u)
{
sol+=bit[k][u];
u-=u&(-u);
}
return sol;
}
bool cmp(int a,int b)
{
if(ql[a]!=ql[b]) return ql[a]<ql[b];
if(qt[a]!=qt[b]) return qt[a]<qt[b];
return false;
}
long long count_rectangles(std::vector<std::vector<int> > a)
{
int n=a.size(),m=a[0].size();
long long sol=0;
for(int i=1;i<n-1;i++)
{
for(int j=0;j<m;j++)
{
while(!st.empty() && a[i][st.top()]<a[i][j]) st.pop();
if(!st.empty() && st.top()+1!=j) s[i][j-1].insert(st.top()+1);
st.push(j);
}
while(!st.empty()) st.pop();
for(int j=m-1;j>=0;j--)
{
while(!st.empty() && a[i][st.top()]<a[i][j]) st.pop();
if(!st.empty() && st.top()-1!=j) s[i][st.top()-1].insert(j+1);
st.push(j);
}
while(!st.empty()) st.pop();
}
for(int j=1;j<m-1;j++)
{
for(int i=1;i<n;i++)
{
for(set<int>::iterator it=s[i][j].begin();it!=s[i][j].end();it++)
{
for(int k=i;k<n-1;k++)
{
if(s[k][j].find(*it)==s[k][j].end()) break;
else {if(k!=i) s[k][j].erase(*it); qx[cnt]=*it; qy[cnt]=j; qt[cnt]=1; ql[cnt]=i; ind[k].push_back(cnt++);}
}
}
s[i][j].clear();
}
}
for(int i=1;i<m-1;i++)
{
for(int j=0;j<n;j++)
{
while(!st.empty() && a[st.top()][i]<a[j][i]) st.pop();
if(!st.empty() && st.top()+1!=j) s[j-1][i].insert(st.top()+1);
st.push(j);
}
while(!st.empty()) st.pop();
for(int j=n-1;j>=0;j--)
{
while(!st.empty() && a[st.top()][i]<a[j][i]) st.pop();
if(!st.empty() && st.top()-1!=j) s[st.top()-1][i].insert(j+1);
st.push(j);
}
while(!st.empty()) st.pop();
}
for(int i=1;i<n-1;i++)
{
for(int j=1;j<m;j++)
{
for(set<int>::iterator it=s[i][j].begin();it!=s[i][j].end();it++)
{
for(int k=j+1;k<m;k++)
{
if(s[i][k].find(*it)==s[i][k].end()) {qx[cnt]=j; qy[cnt]=k-1; [cnt]=2; [cnt]=*it; ind[i].push_back(cnt++); break;}
else s[i][k].erase(*it);
}
}
s[i][j].clear();
}
}
for(int i=1;i<n-1;i++)
{
sort(ind[i].begin(),ind[i].end(),cmp);
for(int j=0;j<ind[i].size();j++)
{
if(qt[ind[i][j]]==1) upd(qx[ind[i][j]],qy[ind[i][j]],1);
else for(int k=qx[ind[i][j]];k<=qy[ind[i][j]];k++) sol+=fnd(k,qy[ind[i][j]]);
}
for(int j=0;j<ind[i].size();j++) if(qt[ind[i][j]]==1) upd(qx[ind[i][j]],qy[ind[i][j]],-1);
ind[i].clear();
}
return sol;
}