제출 #1237204

#제출 시각아이디문제언어결과실행 시간메모리
1237204Muhammad_AneeqRectangles (IOI19_rect)C++20
13 / 100
1615 ms286144 KiB
#include "rect.h" #include <vector> #include <iostream> #include <map> #include <set> using namespace std; #define ll long long int const NM=2500*2500*+10; struct comp { int sz,l,r,u,d; }; int n,m; comp rec[NM]={}; int par[NM]={}; int x[4]; int root(int n) { return (par[n]==n?n:(par[n]=root(par[n]))); } comp comb(comp a,comp b) { comp c; c.sz=a.sz+b.sz; c.l=min(a.l,b.l); c.r=max(a.r,b.r); c.u=min(a.u,b.u); c.d=max(a.d,b.d); return c; } vector<int>vals; bool valid(comp a) { if (a.l==0||a.u==0||a.d==n-1||a.r==m-1) return 0; ll lv=(a.d-a.u)+1,lh=(a.r-a.l)+1; return ((lv*lh)==a.sz); } bool ma(int i,int j) { if (j<0||j>=n*m||vals[j]>vals[i]) return 0; return 1; } bool merge(int u,int v) { u=root(u); v=root(v); if (u==v) return 1; rec[u]=comb(rec[u],rec[v]); par[v]=u; return valid(rec[u]); } long long count_rectangles(vector<vector<int>>a) { n=a.size(),m=a[0].size(); x[0]=m,x[1]=-m,x[2]=-1,x[3]=1; map<int,vector<int>>ind; set<int>s; for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { vals.push_back(a[i][j]); int nm=i*m+j; par[nm]=nm; rec[nm].sz=1; rec[nm].l=rec[nm].r=j; rec[nm].u=rec[nm].d=i; s.insert(a[i][j]); ind[a[i][j]].push_back(nm); } } long long ans=0; for (auto i:s) { set<int>g; for (auto j:ind[i]) { for (auto k:x) { if (ma(j,j+k)) { merge(j,j+k); } } g.insert(root(j)); } for (auto i:g) { if (i!=root(i)||!valid(rec[i])) continue; // cout<<i<<endl; 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...