Submission #1237112

#TimeUsernameProblemLanguageResultExecution timeMemory
1237112Muhammad_AneeqRectangles (IOI19_rect)C++17
0 / 100
5 ms1864 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) { x[0]=m,x[1]=-m,x[2]=-1,x[3]=1; n=a.size(),m=a[0].size(); 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]) { g.insert(j); for (auto k:x) { if (ma(j,j+k)) { int z=root(j); g.erase(z); if (merge(j,j+k)) g.insert(root(j)); } } } for (auto i:g) { if (i!=root(i)||!valid(rec[i])) continue; 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...