제출 #1049257

#제출 시각아이디문제언어결과실행 시간메모리
1049257efedmrlrRectangles (IOI19_rect)C++17
72 / 100
5074 ms574716 KiB
#include "rect.h" // #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define lli long long int #define MP make_pair #define pb push_back #define REP(i,n) for(int i = 0; (i) < (n); (i)++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const double EPS = 0.00001; const int INF = 1e9+500; const int N = 3e5+5; const int ALPH = 26; const int LGN = 25; constexpr int MOD = 1e9+7; int n, m; struct DSU { vector<int> p, sz; vector<int> l, r; vector<int> used; int mx; void reset(int s, int mm) { p.assign(s + 3, -1); sz.assign(s + 3, 0); l.assign(s + 3, INF); r.assign(s + 3, 0); used.assign(s + 3, -1); mx = mm; } void make_set(int x) { p[x] = x; sz[x] = 1; l[x] = r[x] = x; } int find_set(int x) { return p[x] == x ? x : find_set(p[x]); } void union_set(int x, int y) { x = find_set(x); y = find_set(y); if(x == y) return; if(sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; p[y] = x; l[x] = min(l[x], l[y]); r[x] = max(r[x], r[y]); } bool check_val(int x) { return !(l[x] == 0 || r[x] == mx); } }; long long count_rectangles(std::vector<std::vector<int> > a) { n = (int)a.size(); m = (int)a[0].size(); vector<vector<array<int, 3 > > > row(n), col(m); REP(i, n - 1) { if(i == 0) continue; DSU ds; ds.reset(m, m - 1); vector<int> ord; REP(j, m) ord.pb(j); sort(all(ord), [&](int x, int y) { return a[i][x] < a[i][y]; }); int last = -1, lind = 0; for(int k = 0; k < ord.size(); k++) { auto &c = ord[k]; if(a[i][c] != last) { for(int j = lind; j < k; j++) { if(ds.used[ds.find_set(ord[j])] == lind) { continue; } ds.used[ds.find_set(ord[j])] = lind; if(!ds.check_val(ds.find_set(ord[j]))) continue; row[i].pb({ds.l[ds.find_set(ord[j])], ds.r[ds.find_set(ord[j])]}); } last = a[i][c]; lind = k; } ds.make_set(c); if(ds.p[c + 1] != -1) ds.union_set(c, c + 1); if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1); } for(int j = lind; j < ord.size(); j++) { if(ds.used[ds.find_set(ord[j])] == lind) { continue; } ds.used[ds.find_set(ord[j])] = lind; if(!ds.check_val(ds.find_set(ord[j]))) continue; row[i].pb({ds.l[ds.find_set(ord[j])], ds.r[ds.find_set(ord[j])], 0}); } } REP(j, m - 1) { if(j == 0) continue; DSU ds; ds.reset(n, n - 1); vector<int> ord; REP(i, n) ord.pb(i); sort(all(ord), [&](int x, int y) { return a[x][j] < a[y][j]; }); int last = -1, lind = 0; for(int k = 0; k < ord.size(); k++) { auto &c = ord[k]; if(a[c][j] != last) { for(int i = lind; i < k; i++) { if(ds.used[ds.find_set(ord[i])] == lind) { continue; } ds.used[ds.find_set(ord[i])] = lind; if(!ds.check_val(ds.find_set(ord[i]))) continue; col[j].pb({ds.l[ds.find_set(ord[i])], ds.r[ds.find_set(ord[i])]}); } last = a[c][j]; lind = k; } ds.make_set(c); if(ds.p[c + 1] != -1) ds.union_set(c, c + 1); if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1); } for(int i = lind; i < ord.size(); i++) { if(ds.used[ds.find_set(ord[i])] == lind) { continue; } ds.used[ds.find_set(ord[i])] = lind; if(!ds.check_val(ds.find_set(ord[i]))) continue; col[j].pb({ds.l[ds.find_set(ord[i])], ds.r[ds.find_set(ord[i])], 0}); } } // cout << "rows: \n"; // for(int i = 0; i < n; i++) { // cout << "i:" << i << "\n"; // for(auto c : row[i]) { // cout << c[0] << " " << c[1] << "\n"; // } // } map<array<int, 3>, int > mpp; for(int i = n - 1; i >= 0; i--) { for(auto &c : row[i]) { mpp[{i, c[0], c[1]}] = c[2] = mpp[{i + 1, c[0], c[1]}] + 1; } } mpp.clear(); for(int i = m - 1; i >= 0; i--) { for(auto &c : col[i]) { mpp[{i, c[0], c[1]}] = c[2] = mpp[{i + 1, c[0], c[1]}] + 1; } } int ans = 0; for(int i = 0; i < n; i++) { for(auto &c : row[i]) { for(auto cl : col[c[0]]) { if(cl[0] != i) continue; if(cl[1] - cl[0] + 1 <= c[2] && c[1] - c[0] + 1 <= cl[2]) { ans++; } } } } return ans; } // int main() { // int n, m; // cin >> n >> m; // vector<vector<int> > grid(n,vector<int>(m)); // REP(i, n) REP(j, m) { // cin >> grid[i][j]; // } // cout << count_rectangles(grid) << "\n"; // return 0; // }

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

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int k = 0; k  < ord.size(); k++) {
      |                  ~~~^~~~~~~~~~~~
rect.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int j = lind; j < ord.size(); j++) {
      |                     ~~^~~~~~~~~~~~
rect.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for(int k = 0; k < ord.size(); k++) {
      |                  ~~^~~~~~~~~~~~
rect.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int i = lind; i < ord.size(); i++) {
      |                     ~~^~~~~~~~~~~~
#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...