| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 928821 | knon0501 | 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>
using namespace std;
vector<short> b[2505][2505];
vector<short> c[2505][2505];
vector<pair<short,short>> d[2505][2505];
vector<pair<short,short>> e[2505][2505];
short lef[2505][2505];
short rig[2505][2505];
short up[2505][2505];
short down[2505][2505];
vector<vector<short>> v;
long long count_rectangles(std::vector<std::vector<short> > a) {
int n = a.size();
int m = a[0].size();
for(int i=1 ; i<n-1 ; i++){
stack<int> S;
for(int j=0 ; j<m ; j++){
bool flag = true;
while(!S.empty() && a[i][S.top()] <= a[i][j]){
int x = S.top();
if(x +1 <j && flag)
b[x+1][j-1].push_back(i);
if(a[i][S.top()]==a[i][j])flag=false;
S.pop();
}
if(!S.empty() ){
int x = S.top();
lef[i][j] = x;
if(x+1<j && flag)
b[x+1][j-1].push_back(i);
}
else{
lef[i][j]=-1;
}
S.push(j);
}
while(!S.empty())S.pop();
for(int j=m-1; j>=0 ; j--){
while(!S.empty() && a[i][S.top()] <= a[i][j]){
S.pop();
}
if(!S.empty() ){
int x = S.top();
rig[i][j] = x;
}
else{
rig[i][j]=-1;
}
S.push(j);
}
}
for(int i=1 ; i<m-1 ; i++){
stack<int> S;
for(int j=0 ; j<n ; j++){
bool flag = true;
while(!S.empty() && a[S.top()][i] <= a[j][i]){
int x = S.top();
if(x +1 <j && flag)
c[x+1][j-1].push_back(i);
if(a[S.top()][i]==a[j][i])flag=false;
S.pop();
}
if(!S.empty() ){
int x = S.top();
up[j][i]=x;
if(x+1<j && flag)
c[x+1][j-1].push_back(i);
}
else{
up[j][i]=-1;
}
S.push(j);
}
while(!S.empty())S.pop();
for(int j=n-1 ; j>=0 ; j--){
while(!S.empty() && a[S.top()][i] <= a[j][i]){
S.pop();
}
if(!S.empty() ){
int x = S.top();
down[j][i]=x;
}
else{
down[j][i]=-1;
}
S.push(j);
}
}
long long ans = 0;
for(int i=1 ; i<m ; i++){
for(int j=i ; j<m ; j++){
reverse(b[i][j].begin(),b[i][j].end());
int prv = -1;
int y;
for(auto x: b[i][j]){
if(x != prv-1){
if(prv>=0)
d[i][j].push_back({prv,y});
y=x;
}
prv=x;
}
if(prv>=0){
d[i][j].push_back({prv,y});
}
sort(d[i][j].begin(),d[i][j].end());
}
}
for(int i=1 ; i<n ; i++){
for(int j=i ; j<n ; j++){
reverse(c[i][j].begin(),c[i][j].end());
int prv = -1;
int y;
for(auto x: c[i][j]){
if(x != prv-1){
if(prv>=0)
e[i][j].push_back({prv,y});
y=x;
}
prv=x;
}
if(prv>=0){
e[i][j].push_back({prv,y});
}
sort(e[i][j].begin(),e[i][j].end());
}
}
for(int i = 1 ; i<n-1 ; i++){
for(int j=1 ; j<m-1 ; j++){
short x = lef[i][j];
short y = rig[i][j];
short z = up[i][j];
short w = down[i][j];
v.push_back({x,y,z,w});
}
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(auto vv: v){
int x=vv[0];
int y = vv[1];
int z =vv[2];
int w = vv[3];
if(x==-1 ||y==-1 || z==-1 || w==-1)continue;
auto k = upper_bound(d[x+1][y-1].begin(),d[x+1][y-1].end(),(pair<short,short>){z+1,1e9});
if(k== d[x+1][y-1].begin())continue;
if((--k)->second <w-1)continue;
//cout<<z+1<<" "<<w-1<<" "<<e[z+1][w-1].size()<<" "<<c[z+1][w-1].size()<<endl;
auto t = upper_bound(e[z+1][w-1].begin(),e[z+1][w-1].end(),(pair<short,short>){x+1,1e9});
if(t== e[z+1][w-1].begin())continue;
if((--t)->second <y-1)continue;
ans++;
}
return ans;
}