제출 #199629

#제출 시각아이디문제언어결과실행 시간메모리
199629medkRectangles (IOI19_rect)C++14
59 / 100
5066 ms360204 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; map<pair<int,int>,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); } void connect(int i, int j) { i=getp(i), 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]; } ll count_rectangles(vector<vector<int>> a) { for(int i=0;i<2500;i++) dsu.pb({i,{i,i}}), sz.pb(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]++; if(vp[j].y!=m-1) if(tmp[vp[j].y+1]==i) connect(vp[j].y, vp[j].y+1); if(vp[j].y!=0) if(tmp[vp[j].y-1]==i) connect(vp[j].y, vp[j].y-1); int par=getp(vp[j].y); 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(mp.count({i-1,l2-1})) { auto it = mp[{i-1,l2-1}].lower_bound({l+1,0}); if(it!=mp[{i-1,l2-1}].end()) if((*it).x==l+1) num+=(*it).y; } mp[{i,l2-1}].insert({l+1,num}); num=1; if(mp.count({i-1,l+1})) { auto it = mp[{i-1,l+1}].lower_bound({l2-1,0}); if(it!=mp[{i-1,l+1}].end()) if((*it).x==l2-1) num+=(*it).y; } mp[{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]++; if(vp[j].y!=n-1) if(tmp[vp[j].y+1]==i) connect(vp[j].y, vp[j].y+1); if(vp[j].y!=0) if(tmp[vp[j].y-1]==i) connect(vp[j].y, vp[j].y-1); int par=getp(vp[j].y); 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(mp2.count({l2-1,i-1})) { auto it = mp2[{l2-1,i-1}].lower_bound({l+1,0}); if(it!=mp2[{l2-1,i-1}].end()) if((*it).x==l+1) num+=(*it).y; } mp2[{l2-1,i}].insert({l+1,num}); num=1; if(mp2.count({l+1,i-1})) { auto it = mp2[{l+1,i-1}].lower_bound({l2-1,0}); if(it!=mp2[{l+1,i-1}].end()) if((*it).x==l2-1) num+=(*it).y; } mp2[{l+1,i}].insert({l2-1,num}); auto it = mp[{l,i+1}].lower_bound({i-num,l-l2+1}); for(;it!=mp[{l,i+1}].end();it++) { if((*it).x>i+1) break; if((*it).y>=l-l2+1) ans++; } } } return ans; } /* int main() { freopen("test.in","r",stdin); int n,m; cin>>n>>m; vector<vector<int>> a(n); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { int k; cin>>k; a[i].pb(k); } cout<<count_rectangles(a); } */
#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...