Submission #1073466

#TimeUsernameProblemLanguageResultExecution timeMemory
1073466n1kRectangles (IOI19_rect)C++17
0 / 100
1335 ms360612 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; int n, m; vector<vector<array<int, 3>>> h; vector<vector<array<int, 2>>> get(){ vector<vector<array<int, 2>>> l(n, vector<array<int, 2>>(m)); for(int r=1; r+1<h.size(); r++){ vector<array<int, 3>> st = {{h[r][0]}}; for(int c=1; c+1<h[0].size(); c++){ while(st.size() and st.back()[0]<=h[r][c][0]){ st.pop_back(); } l[h[r][c][1]][h[r][c][2]] = (st.size()?array<int, 2>{st.back()[1], st.back()[2]}:array<int, 2>{-1, -1}); st.push_back(h[r][c]); } } return l; } void rot(){ vector<vector<array<int, 3>>> hh(h[0].size(), vector<array<int, 3>>(h.size())); for(int r=0; r<h.size(); r++){ for(int c=0; c<h[0].size(); c++){ hh[c][h.size() - r - 1] = h[r][c]; } } h = hh; } long long count_rectangles(vector<vector<int>> a) { n = a.size(), m = a[0].size(); h.assign(a.size(), vector<array<int, 3>>(a[0].size())); vector<array<int, 2>> order; for(int r=0; r<a.size(); r++){ for(int c=0; c<a[0].size(); c++){ h[r][c] = {a[r][c], r, c}; } } auto l=get(); rot(); auto d = get(); rot(); auto ri = get(); rot(); auto u = get(); rot(); auto find = [&](int r1, int r2, int c1, int c2){ array<int, 3> ll={int(1e9)}, dd={int(-1e9)}, riri={int(-1e9)}, uu={int(1e9)}; for(int r=r1+1; r<r2; r++){ for(int c=c1+1; c<c2; c++){ ll = min(ll, {l[r][c][1], r, c}); dd = max(dd, {d[r][c][0], r, c}); riri = max(riri, {ri[r][c][1], r, c}); uu = min(uu, {u[r][c][0], r, c}); } } set<array<int, 2>> s; s.insert({ll[1], ll[2]}); s.insert({dd[1], dd[2]}); s.insert({riri[1], riri[2]}); s.insert({uu[1], uu[2]}); return s; }; vector g(n, vector<vector<array<int, 2>>>(m)); for(int r=1; r+1<n; r++){ for(int c=1; c+1<m; c++){ // find() int r1 = u[r][c][0], r2 = d[r][c][0]; int c1 = l[r][c][1], c2 = ri[r][c][1]; if(min({r1, r2, c1, c2})==-1){ g[r][c].push_back({-1, -1}); }else{ for(auto p:find(r1, r2, c1, c2)){ g[r][c].push_back(p); } } } } vector mem(n, vector<int>(m, -1)); vector vis(n, vector<int>(m)); vector bd(n, vector<int>(m)); function<void(int, int)> dfsord = [&](int r, int c){ if(vis[r][c]) return; vis[r][c]=1; int r1 = u[r][c][0], r2 = d[r][c][0]; int c1 = l[r][c][1], c2 = ri[r][c][1]; if(min({r1, r2, c1, c2})==-1){ bd[r][c] = 1; return; } for(int rr=r1+1; rr<r2; rr++){ for(int cc=c1+1; cc<c2; cc++){ bd[r][c] |= bd[rr][cc]; dfsord(rr, cc); } } if(not bd[r][c]) order.push_back({r, c}); }; for(int r=1; r+1<n; r++){ for(int c=1; c+1<m; c++){ if(vis[r][c]) continue; dfsord(r, c); } } function<void(int, int)> dfs = [&](int r, int c){ if(vis[r][c]) return; vis[r][c]=1; if(mem[r][c]!=-1) mem[r][c]; bool ok = 1; for(auto [rr, cc]:g[r][c]){ if(rr==r and cc==c){ continue; } if(rr==-1 and cc==-1){ ok = 0; continue; } dfs(rr, cc); ok &= mem[rr][cc]; l[r][c][1] = min(l[r][c][1], l[rr][cc][1]); d[r][c][0] = max(d[r][c][0], d[rr][cc][0]); ri[r][c][1] = max(ri[r][c][1], ri[rr][cc][1]); u[r][c][0] = min(u[r][c][0], u[rr][cc][0]); } mem[r][c] = ok; }; vis.assign(n, vector<int>(m)); long long ans = 0; for(auto [r, c]:order){ if(vis[r][c]) continue; dfs(r, c); assert(mem[r][c]!=-1); ans += mem[r][c]; if(mem[r][c]){ for(int rr=u[r][c][0]+1; rr<d[r][c][0]; rr++){ for(int cc=l[r][c][1]+1; cc<ri[r][c][1]; cc++){ mem[rr][cc] = mem[r][c]; vis[rr][cc] = 1; } } } if(mem[r][c]==1){ } } // build graph /* for(int r=0; r<n; r++){ for(int c=0; c<m; c++){ cerr<<mark[r][c]<<" "; } cerr<<endl; } for(int r=0; r<u.size();r++){ for(int c=0; c<u[0].size(); c++){ cerr<<u[r][c][0]<<" "<<u[r][c][1]<<" | "; } cerr<<endl; } for(int r=0; r<h.size(); r++){ for(int c=0; c<h[0].size(); c++){ cerr<<h[r][c][0]<<" "; } cerr<<endl; } */ return ans; }

Compilation message (stderr)

rect.cpp: In function 'std::vector<std::vector<std::array<int, 2> > > get()':
rect.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int r=1; r+1<h.size(); r++){
      |               ~~~^~~~~~~~~
rect.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int c=1; c+1<h[0].size(); c++){
      |                ~~~^~~~~~~~~~~~
rect.cpp: In function 'void rot()':
rect.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int r=0; r<h.size(); r++){
      |               ~^~~~~~~~~
rect.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int c=0; c<h[0].size(); c++){
      |                ~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int r=0; r<a.size(); r++){
      |               ~^~~~~~~~~
rect.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int c=0; c<a[0].size(); c++){
      |                ~^~~~~~~~~~~~
#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...