제출 #479443

#제출 시각아이디문제언어결과실행 시간메모리
479443peti1234Rectangles (IOI19_rect)C++17
59 / 100
2455 ms1048580 KiB
#include <bits/stdc++.h> using namespace std; const int c=5002; bool v[c][c], t[c][c]; int n, m, ans, ks, ko, ns, no, mini, db, fel[c][c], le[c][c], bal[c][c], jobb[c][c]; vector<pair<pair<int, int>, pair<int, int> > > ch; void add(int a, int b, int c, int d) {ch.push_back({{a, b}, {c, d}});} long long count_rectangles(vector<vector<int>> sz) { n=sz.size(), m=sz[0].size(); vector<int> s; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { while(s.size()>0 && sz[i][j]>=sz[i][s.back()]) jobb[i][1+s.back()]=j-1, s.pop_back(); s.push_back(j); } while(s.size()>0) jobb[i][1+s.back()]=-1, s.pop_back(); for (int j=m-1; j>=0; j--) { while(s.size()>0 && sz[i][j]>=sz[i][s.back()]) bal[i][-1+s.back()]=j+1, s.pop_back(); if (j) s.push_back(j); } while(s.size()>0) bal[i][-1+s.back()]=-1, s.pop_back(); } for (int j=0; j<m; j++) { for (int i=0; i<n; i++) { while(s.size()>0 && sz[i][j]>=sz[s.back()][j]) le[1+s.back()][j]=i-1, s.pop_back(); s.push_back(i); } while(s.size()>0) le[1+s.back()][j]=-1, s.pop_back(); for (int i=n-1; i>=0; i--) { while(s.size()>0 && sz[i][j]>=sz[s.back()][j]) fel[-1+s.back()][j]=i+1, s.pop_back(); if (i) s.push_back(i); } while(s.size()>0) fel[-1+s.back()][j]=-1, s.pop_back(); } /*cout << "fel\n"; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { cout << fel[i][j] << " "; } cout << "\n"; }*/ for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { int ba=bal[i][j], jo=jobb[i][j], fe=fel[i][j], l=le[i][j]; add(i, j, l, jo), add(i, ba, l, j), add(fe, j, i, jo), add(fe, ba, i, j); if (jo!=-1) add(i, j, le[i][jo], jo); if (l!=-1) add(i, j, l, jobb[l][j]); } } sort(ch.begin(), ch.end()); for (int i=0; i<ch.size(); i++) if (i==0 || ch[i]!=ch[i-1]) { ks=ch[i].first.first, ko=ch[i].first.second, ns=ch[i].second.first, no=ch[i].second.second, mini=min({ks, ko, ns, no}); if (mini!=-1 && ks && ko && ns<n-1 && no<m-1 && ks<=ns && ko<=no) { int r=0; for (int j=ko; j<=no; j++) { if (le[ks][j]!=-1 && le[ks][j]<ns) r++; if (fel[ns][j]>ks) r++; if (r) break; } for (int i=ks; i<=ns; i++) { if (jobb[i][ko]!=-1 && jobb[i][ko]<no) r++; if (bal[i][no]>ko) r++; if (r) break; } if (!r) ans++; } } return ans; } /* int b1, b2; vector<vector<int>> b3; int main() { cin >> b1 >> b2; b3.resize(b1); for (int i=0; i<b1; i++) for (int j=0; j<b2; j++) { int x; cin >> x; b3[i].push_back(x); } cout << count_rectangles(b3); return 0; } */ /* 6 5 4 8 7 5 6 7 4 10 3 5 9 7 20 14 2 9 14 7 5 6 5 7 5 2 7 4 5 13 5 6 */

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i=0; i<ch.size(); i++) if (i==0 || ch[i]!=ch[i-1]) {
      |                   ~^~~~~~~~~~
#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...