제출 #199909

#제출 시각아이디문제언어결과실행 시간메모리
199909medkRectangles (IOI19_rect)C++14
72 / 100
5097 ms922884 KiB
#include <bits/stdc++.h> #include "rect.h" #define ll long long #define pb push_back #define x first #define y second using namespace std; int where[2500][2500],where2[2500][2500]; vector<set<pair<int,int>>> mp,mp2; vector<pair<int,pair<int,int>>> dsu; vector<int> sz; int getp(int x) { if (x==dsu[x].x) return x; return dsu[x].x=getp(dsu[x].x); } int connect(int i, int j) { j=getp(j); if(sz[i]<sz[j]) swap(i,j); dsu[j].x=i; dsu[i].y.x=max(dsu[i].y.x,dsu[j].y.x); dsu[i].y.y=min(dsu[i].y.y,dsu[j].y.y); sz[i]+=sz[j]; return i; } ll count_rectangles(vector<vector<int>> a) { for(int i=0;i<2500;i++) dsu.pb({i,{i,i}}), sz.pb(1); for(int i=0;i<2500;i++) for(int j=0;j<2500;j++) where[i][j]=-1,where2[i][j]=-1; vector<pair<int,pair<int,int>>> dsuin=dsu; int n=a.size(), m=a[0].size(); vector<int> tmp(2500,0); for(int i=1;i<n-1;i++) { dsu=dsuin; fill(sz.begin(),sz.end(),1); vector<pair<int,int>> vp; for(int j=0;j<m;j++) vp.pb({a[i][j],j}); sort(vp.begin(),vp.end()); for(int j=0;j<m;j++) { tmp[vp[j].y]++; int par=getp(vp[j].y); if(vp[j].y!=m-1) if(tmp[vp[j].y+1]==i) par=connect(par, vp[j].y+1); if(vp[j].y!=0) if(tmp[vp[j].y-1]==i) par=connect(par, vp[j].y-1); int l=dsu[par].y.x, l2=dsu[par].y.y; if(l2==0 || l==m-1) continue; if(a[i][l+1]==vp[j].x || a[i][l2-1]==vp[j].x) continue; int num=1; if(where[i-1][l+1]!=-1) { auto it = mp[where[i-1][l+1]].lower_bound({l2-1,0}); if(it!=mp[where[i-1][l+1]].end()) if((*it).x==l2-1) num+=(*it).y; } if(where[i][l+1]==-1) where[i][l+1]=mp.size(), mp.pb(set<pair<int,int>>()); mp[where[i][l+1]].insert({l2-1,num}); } } ll ans=0; for(int i=0;i<2500;i++) tmp[i]=0; for(int i=1;i<m-1;i++) { dsu=dsuin; fill(sz.begin(),sz.end(),1); vector<pair<int,int>> vp; for(int j=0;j<n;j++) vp.pb({a[j][i],j}); sort(vp.begin(),vp.end()); for(int j=0;j<n;j++) { tmp[vp[j].y]++; int par=getp(vp[j].y); if(vp[j].y!=n-1) if(tmp[vp[j].y+1]==i) par=connect(par, vp[j].y+1); if(vp[j].y!=0) if(tmp[vp[j].y-1]==i) par=connect(par, vp[j].y-1); int l=dsu[par].y.x, l2=dsu[par].y.y; if(l2==0 || l==n-1) continue; if(a[l+1][i]==vp[j].x || a[l2-1][i]==vp[j].x) continue; int num=1; if(where2[l+1][i-1]!=-1) { auto it = mp2[where2[l+1][i-1]].lower_bound({l2-1,0}); if(it!=mp2[where2[l+1][i-1]].end()) if((*it).x==l2-1) num+=(*it).y; } if(where2[l+1][i]==-1) where2[l+1][i]=mp2.size(), mp2.pb(set<pair<int,int>>()); mp2[where2[l+1][i]].insert({l2-1,num}); if(where[l][i+1]!=-1) { auto it = mp[where[l][i+1]].lower_bound({i-num,l-l2+1}); for(;it!=mp[where[l][i+1]].end();it++) { if((*it).x>i+1) break; if((*it).y>=l-l2+1) ans++; } } } } return ans; }
#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...