Submission #226524

#TimeUsernameProblemLanguageResultExecution timeMemory
226524tinjyuRectangles (IOI19_rect)C++14
72 / 100
5098 ms682632 KiB
#include "rect.h" #include <iostream> #include <cmath> #include <algorithm> using namespace std; struct node{ int x, y; }array[7000000]; int u[2505][2505],d[2505][2505],tree1[2505][10005][2],tree2[2505][10005][2],n,m,s[2505][2505][2],l[2505][2505],st2[2505][2505][2],r[2505][2505],t[10005][2],bits[20]; int findtree1(int le,int ri,int j,int st,int en,int t,int opt) { if(le>en || ri<st) { if(opt==0)return -1; return 5000; } if(st>=le && en<=ri) { return tree1[j][t][opt]; } if(opt==0)return max(findtree1(le,ri,j,st,(st+en)/2,t*2,opt),findtree1(le,ri,j,(st+en)/2+1,en,t*2+1,opt)); else return min(findtree1(le,ri,j,st,(st+en)/2,t*2,opt),findtree1(le,ri,j,(st+en)/2+1,en,t*2+1,opt)); } int findtree2(int le,int ri,int i,int st,int en,int t,int opt) { //cout<<le<<" "<<ri<<" "<<i<<" "<<st<<" "<<en<<" "<<opt<<" "<<t<<" "<<tree2[i][t][opt]<<endl; if(le>en || ri<st) { if(opt==0)return -1; return 5000; } if(st>=le && en<=ri) { return tree2[i][t][opt]; } if(opt==0)return max(findtree2(le,ri,i,st,(st+en)/2,t*2,opt),findtree2(le,ri,i,(st+en)/2+1,en,t*2+1,opt)); else return min(findtree2(le,ri,i,st,(st+en)/2,t*2,opt),findtree2(le,ri,i,(st+en)/2+1,en,t*2+1,opt)); } long long int find(int i,int j) { long long int x1=l[i][j],y1=u[i][j],x2=r[i][j],y2=d[i][j]; long long int le=l[i][j]+1,ri=r[i][j]-1; long long int k=log2(ri-le+1); //cout<<y1<<" "<<x1<<" "<<y2<<" "<<x2<<" "<<le<<" "<<ri<<endl; long long int tmp=findtree2(le,ri,y1,0,m-1,1,1); //cout<<tmp<<endl; if( tmp < y2 ) return 0; tmp=findtree2(le,ri,y2,0,m-1,1,0); //cout<<tmp<<endl; if( tmp > y1 ) return 0; long long int up=u[i][j]+1,down=d[i][j]-1; k=log2(down-up+1); tmp=findtree1(up,down,x1,0,n-1,1,1); //cout<<tmp<<endl; if( tmp < x2 )return 0; tmp=findtree1(up,down,x2,0,n-1,1,0); //cout<<tmp<<endl; if( tmp > x1 )return 0; return 1; } bool cmp(node ax,node ay) { long long int ar[10][4]; ar[0][0]=u[ax.x][ax.y]; ar[0][1]=l[ax.x][ax.y]; ar[0][2]=d[ax.x][ax.y]; ar[0][3]=r[ax.x][ax.y]; ar[1][0]=u[ay.x][ay.y]; ar[1][1]=l[ay.x][ay.y]; ar[1][2]=d[ay.x][ay.y]; ar[1][3]=r[ay.x][ay.y]; for(int i=0;i<4;i++) { if(ar[0][i]<ar[1][i])return 1; if(ar[0][i]>ar[1][i])return 0; } return 0; } void build1(int j,int st,int e,int t) { if(st==e) { tree1[j][t][0]=st2[st][j][0]; tree1[j][t][1]=st2[st][j][1]; //cout<<j<<" "<<st<<" "<<e<<" "<<t<<" "<<tree1[j][t][0]<<" "<<tree1[j][t][1]<<endl; return ; } build1(j,st,(st+e)/2,t*2); build1(j,(st+e)/2+1,e,t*2+1); tree1[j][t][0]=max(tree1[j][t*2][0],tree1[j][t*2+1][0]); tree1[j][t][1]=min(tree1[j][t*2][1],tree1[j][t*2+1][1]); //cout<<j<<" "<<st<<" "<<e<<" "<<t<<" "<<tree1[j][t][0]<<" "<<tree1[j][t][1]<<endl; return ; } void build2(int i,int st,int e,int t) { if(st==e) { tree2[i][t][0]=s[i][st][0]; tree2[i][t][1]=s[i][st][1]; //cout<<i<<" "<<st<<" "<<e<<" "<<t<<" "<<tree2[i][t][0]<<" "<<tree2[i][t][1]<<endl; return ; } build2(i,st,(st+e)/2,t*2); build2(i,(st+e)/2+1,e,t*2+1); tree2[i][t][0]=max(tree2[i][t*2][0],tree2[i][t*2+1][0]); tree2[i][t][1]=min(tree2[i][t*2][1],tree2[i][t*2+1][1]); //cout<<i<<" "<<st<<" "<<e<<" "<<t<<" "<<tree2[i][t][0]<<" "<<tree2[i][t][1]<<endl; return ; } long long count_rectangles(std::vector<std::vector<int> > a) { n=a.size(); m=a[0].size(); for(int i=0;i<n;i++) { long long int p=0,st=0,en=-1; for(int j=0;j<m;j++) { l[i][j]=-1; r[i][j]=5000; for(int k=en;k>=st;k--) { if(a[i][j]>t[k][0]) { r[i][t[k][1]]=j; en--; } else { en++; t[en][0]=a[i][j]; t[en][1]=j; if(a[i][j]<t[k][0])l[i][j]=t[k][1]; else l[i][j]=l[i][t[k][1]]; break; } } if(en==-1) { en=0; t[en][0]=a[i][j]; t[en][1]=j; } } } for(int j=0;j<m;j++) { long long int p=0,st=0,en=-1; for(int i=0;i<n;i++) { u[i][j]=-1; d[i][j]=5000; for(int k=en;k>=st;k--) { if(a[i][j]>t[k][0]) { d[t[k][1]][j]=i; en--; } else { en++; t[en][0]=a[i][j]; t[en][1]=i; if(a[i][j]<t[k][0])u[i][j]=t[k][1]; else u[i][j]=u[t[k][1]][j]; break; } } if(en==-1) { en=0; t[en][0]=a[i][j]; t[en][1]=i; } } } for(int i=0;i<n;i++) { long long int p=0,st=0,en=-1; for(int j=0;j<m;j++) { st2[i][j][0]=-1; st2[i][j][1]=5000; for(int k=en;k>=st;k--) { if(a[i][j]>=t[k][0]) { st2[i][t[k][1]][1]=j; en--; if(a[i][j]==t[k][0]) { st2[i][j][0]=t[k][1]; en++; t[en][0]=a[i][j]; t[en][1]=j; break; } } else { en++; t[en][0]=a[i][j]; t[en][1]=j; st2[i][j][0]=t[k][1]; break; } } if(en==-1) { en=0; t[en][0]=a[i][j]; t[en][1]=j; } } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { //cout<<st2[i][j][0]<<" "<<st2[i][j][1]<<endl; } } for(int j=0;j<m;j++) { long long int p=0,st=0,en=-1; for(int i=0;i<n;i++) { s[i][j][0]=-1; s[i][j][1]=5000; for(int k=en;k>=st;k--) { if(a[i][j]>=t[k][0]) { s[t[k][1]][j][1]=i; en--; if(a[i][j]==t[k][0]) { s[i][j][0]=t[k][1]; en++; t[en][0]=a[i][j]; t[en][1]=i; break; } } else { en++; t[en][0]=a[i][j]; t[en][1]=i; s[i][j][0]=t[k][1]; break; } } if(en==-1) { en=0; t[en][0]=a[i][j]; t[en][1]=i; } } } //cout<<st2[4][16][0][1]<<endl; bits[0]=1; for(int i=0;i<m;i++) { build1(i,0,n-1,1); } //cout<<endl; for(int j=0;j<n;j++) { build2(j,0,m-1,1); } long long int ans=0; long long int cnt=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(u[i][j]==-1 || d[i][j]==5000 || l[i][j]==-1 || r[i][j]==5000)continue; //if((a[i-1][j]==a[i][j] && i!=1) || (a[i][j-1]==a[i][j] && j!=1))continue; cnt++; array[cnt].x=i; array[cnt].y=j; } } sort(array+1,array+cnt+1,cmp); //cout<<cnt<<endl; for(int i=1;i<=cnt;i++) { long long int x=array[i].x,y=array[i].y,x1=array[i-1].x,y1=array[i-1].y; if(u[x][y]==u[x1][y1] && d[x][y]==d[x1][y1] && l[x][y]==l[x1][y1] && r[x][y]==r[x1][y1])continue; //cout<<x<<" "<<y<<endl; long long int tmp=find(x,y); if(tmp==1) //cout<<u[x][y]+1<<" "<<l[x][y]+1<<" "<<d[x][y]-1<<" "<<r[x][y]-1<<endl; //cout<<endl; ans+=tmp; } return ans; }

Compilation message (stderr)

rect.cpp: In function 'long long int find(int, int)':
rect.cpp:44:16: warning: variable 'k' set but not used [-Wunused-but-set-variable]
  long long int k=log2(ri-le+1);
                ^
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:121:17: warning: unused variable 'p' [-Wunused-variable]
   long long int p=0,st=0,en=-1;
                 ^
rect.cpp:153:17: warning: unused variable 'p' [-Wunused-variable]
   long long int p=0,st=0,en=-1;
                 ^
rect.cpp:186:17: warning: unused variable 'p' [-Wunused-variable]
   long long int p=0,st=0,en=-1;
                 ^
rect.cpp:232:17: warning: unused variable 'p' [-Wunused-variable]
   long long int p=0,st=0,en=-1;
                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...