| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 443413 | vanic | Rectangles (IOI19_rect) | C++14 | 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 <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int maxn=2503, Log=12, pot=(1<<Log);
const int inf=1e9;
int R1[maxn][maxn][Log], C1[maxn][maxn][Log], R2[maxn][maxn][Log], C2[maxn][maxn][Log], R3[maxn][maxn][Log], C3[maxn][maxn][Log], R4[maxn][maxn][Log], C4[maxn][maxn][Log];
int gore[maxn][Log], dolje[maxn][Log];
ll sol;
int svi[maxn][maxn][4];
int n, m;
map < ll, bool > bio;
int svi1[maxn][maxn][4];
int query1(int y, int l, int d){
int raz=d-l+1;
int x=log2(raz);
return min(R1[y][l][x], R2[y][d][x]);
}
int query2(int y, int l, int d){
int raz=d-l+1;
int x=log2(raz);
return max(R3[y][l][x], R4[y][d][x]);
}
int query3(int y, int l, int d){
int raz=d-l+1;
int x=log2(raz);
return min(C1[l][y][x], C2[d][y][x]);
}
int query4(int y, int l, int d){
int raz=d-l+1;
int x=log2(raz);
return max(C3[l][y][x], C4[d][y][x]);
}
ll count_rectangles(vector < vector < int > > a){
n=a.size();
m=a[0].size();
vector < pair <int, int > > v;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
while(!v.empty() && v.back().first<a[i][j]){
v.pop_back();
}
if(v.empty()){
svi1[i][j][2]=0;
}
else{
svi1[i][j][2]=v.back().second+1;
}
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][2]=0;
}
else{
svi[i][j][2]=v.back().second+1;
}
v.push_back({a[i][j], j});
}
v.clear();
for(int j=m-1; j>-1; j--){
while(!v.empty() && v.back().first<a[i][j]){
v.pop_back();
}
if(v.empty()){
svi1[i][j][3]=m-1;
}
else{
svi1[i][j][3]=v.back().second-1;
}
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][3]=m-1;
}
else{
svi[i][j][3]=v.back().second-1;
}
v.push_back({a[i][j], j});
}
v.clear();
}
for(int j=0; j<m; j++){
for(int i=0; i<n; i++){
while(!v.empty() && v.back().first<a[i][j]){
v.pop_back();
}
if(v.empty()){
svi1[i][j][0]=0;
}
else{
svi1[i][j][0]=v.back().second+1;
}
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][0]=0;
}
else{
svi[i][j][0]=v.back().second+1;
}
v.push_back({a[i][j], i});
}
v.clear();
for(int i=n-1; i>-1; i--){
while(!v.empty() && v.back().first<a[i][j]){
v.pop_back();
}
if(v.empty()){
svi1[i][j][1]=n-1;
}
else{
svi1[i][j][1]=v.back().second-1;
}
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][1]=n-1;
}
else{
svi[i][j][1]=v.back().second-1;
}
v.push_back({a[i][j], i});
}
v.clear();
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
R1[i][j][0]=svi1[i][j][1];
R2[i][j][0]=svi1[i][j][1];
R3[i][j][0]=svi1[i][j][0];
R4[i][j][0]=svi1[i][j][0];
C1[i][j][0]=svi1[i][j][3];
C2[i][j][0]=svi1[i][j][3];
C3[i][j][0]=svi1[i][j][2];
C4[i][j][0]=svi1[i][j][2];
}
}
for(int i=0; i<m; i++){
gore[i][0]=min(i+1, m-1);
dolje[i][0]=max(i-1, 0);
}
for(int i=1; i<Log; i++){
for(int j=0; j<m; j++){
gore[j][i]=gore[gore[j][i-1]][i-1];
dolje[j][i]=dolje[dolje[j][i-1]][i-1];
for(int k=0; k<n; k++){
R1[k][j][i]=min(R1[k][j][i-1], R1[k][gore[j][i-1]][i-1]);
R2[k][j][i]=min(R2[k][j][i-1], R2[k][dolje[j][i-1]][i-1]);
R3[k][j][i]=max(R3[k][j][i-1], R3[k][gore[j][i-1]][i-1]);
R4[k][j][i]=max(R4[k][j][i-1], R4[k][dolje[j][i-1]][i-1]);
}
}
}
for(int i=0; i<n; i++){
gore[i][0]=min(i+1, n-1);
dolje[i][0]=max(i-1, 0);
}
for(int i=1; i<Log; i++){
for(int j=0; j<n; j++){
gore[j][i]=gore[gore[j][i-1]][i-1];
dolje[j][i]=dolje[dolje[j][i-1]][i-1];
for(int k=0; k<m; k++){
C1[j][k][i]=min(C1[j][k][i-1], C1[gore[j][i-1]][k][i-1]);
C2[j][k][i]=min(C2[j][k][i-1], C2[dolje[j][i-1]][k][i-1]);
C3[j][k][i]=max(C3[j][k][i-1], C3[gore[j][i-1]][k][i-1]);
C4[j][k][i]=max(C4[j][k][i-1], C4[dolje[j][i-1]][k][i-1]);
}
}
}
int c[4];
ll br;
for(int i=1; i<n-1; i++){
for(int j=1; j<m-1; j++){
br=0;
for(int k=0; k<4; k++){
c[k]=svi[i][j][k];
br*=maxn;
br+=c[k];
}
if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1 || bio.find(br)!=bio.end()){
continue;
}
/* if(i==3 && j==3){
cout << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << c[3] << endl;
// cout << query2(c[2], c[3]) << endl;
}*/
if(c[0]<query2(c[1]+1, c[2], c[3])){
continue;
}
if(c[1]>query1(c[0]-1, c[2], c[3])){
continue;
}
if(c[2]<query4(c[3]+1, c[0], c[1])){
continue;
}
if(c[3]>query3(c[2]-1, c[0], c[1])){
continue;
}
bio[br]=1;
// cout << c[0] << ' '<< c[2] << ' ' << c[1] << ' ' << c[3] << endl;
sol++;
}
}
return sol;
}