제출 #298106

#제출 시각아이디문제언어결과실행 시간메모리
298106erd1Rectangles (IOI19_rect)C++14
72 / 100
5144 ms956280 KiB
#include "rect.h" #include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back #define all(x) (x).begin(), (x).end() typedef int64_t lld; typedef pair<int, int> pii; /* #include<bits/extc++.h> using namespace __gnu_pbds; template<typename T, typename comp = greater<T>> using OST = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>; */ template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> p){ return out << "(" << p.ff << ", " << p.ss << ")"; } vector<pii> tmp; vector<vector<int16_t>> U, D, L, R, t, ans; vector<vector<bool>> ansb; vector<int16_t> dsu, sz, rtx; void init(){ iota(all(dsu), 0); fill(all(sz), 1); iota(all(rtx), 0); } int16_t root(int i){ return dsu[i] == i? i: dsu[i] = root(dsu[i]); } void join(int16_t i, int16_t j){ i = root(i), j = root(j); int16_t u = j; if(sz[i] > sz[j])swap(i, j); dsu[i] = j; rtx[j] = u; } struct node{ node *L, *R; int16_t l, r; vector<vector<pair<int16_t, pair<int16_t, int16_t>>>> queries; node(int16_t ll, int16_t rr, int16_t m){ queries.resize(m); l = ll, r = rr; if(l != r)L = new node(l, l+r>>1, m), R = new node((l+r>>1)+1, r, m); } void add(int16_t ll, int16_t rr, int16_t l2, int16_t r2, int16_t x, int16_t y){ if(ll > r || rr < l)return; if(ll <= l && r <= rr)queries[r2].pb({l2, {x, y}}); else L->add(ll, rr, l2, r2, x, y), R->add(ll, rr, l2, r2, x, y); } void answer(const vector<int16_t>& v, function<bool(int16_t, int16_t)> cmp){ init(); tmp.resize(0); for(int i = 0; i < v.size(); i++){ while(tmp.size() && cmp(v[i], tmp.back().ff))join(tmp.back().ss, i), tmp.pop_back(); tmp.pb({v[i], i}); for(auto p: queries[i]) // if(ans[p.ss.ff][p.ss.ss] == -2 || cmp(v[root(p.ff)], ans[p.ss.ff][p.ss.ss])) ans[p.ss.ff][p.ss.ss] = v[rtx[root(p.ff)]]; } } void process(vector<vector<int16_t>>& v, function<bool(int16_t, int16_t)> cmp){ //cout << "process" << l << " " << r << endl; if(l != r){ L->process(v, cmp), R->process(v, cmp); for(int i = 0; i < v[l].size(); i++) v[l][i] = cmp(v[l][i], v[(l+r>>1)+1][i])?v[l][i]:v[(l+r>>1)+1][i]; } answer(v[l], cmp); //cout << "end_process" << l << " " << r << endl; } } *rt; vector<tuple<int16_t, int16_t, int16_t, int16_t>> st; long long count_rectangles(vector<vector<int>> a) { int n = a.size(), m = a[0].size(); ans.resize(n); for(auto& i: ans)i.resize(m); ansb.resize(n); for(auto& i: ansb)i.resize(m, 1); dsu.resize(m); rtx.resize(m); sz.resize(m, 1); U = D = L = R = ans; for(int i = 1; i < n; i++){ tmp.resize(0); tmp.pb({INT_MAX, -1}); for(int j = 0; j < m; j++){ while(tmp.back().ff <= a[i][j])tmp.pop_back(); L[i][j] = tmp.back().ss; tmp.pb({a[i][j], j}); } tmp.resize(0); tmp.pb({INT_MAX, m}); for(int j = m-1; j > 0; j--){ while(tmp.back().ff <= a[i][j])tmp.pop_back(); R[i][j] = tmp.back().ss; tmp.pb({a[i][j], j}); } } for(int j = 1; j < m; j++){ tmp.resize(0); tmp.pb({INT_MAX, -1}); for(int i = 0; i < n; i++){ while(tmp.back().ff <= a[i][j])tmp.pop_back(); U[i][j] = tmp.back().ss; tmp.pb({a[i][j], i}); } tmp.resize(0); tmp.pb({INT_MAX, n}); for(int i = n-1; i > 0; i--){ while(tmp.back().ff <= a[i][j])tmp.pop_back(); D[i][j] = tmp.back().ss; tmp.pb({a[i][j], i}); } } rt = new node(0, n-1, m); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(!(U[i][j] < 0 || D[i][j] >= n || L[i][j] < 0 || R[i][j] >= m)) rt->add(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1, i, j); for(auto& i: ans)fill(all(i), -2); t = U, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false; for(auto& i: ans)fill(all(i), -2); t = L, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false; for(auto& i: ans)fill(all(i), -2); t = D, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false; for(auto& i: ans)fill(all(i), -2); t = R, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false; //cout << "hi" << endl; //u.init(n, m), d.init(n, m), l.init(n, m), r.init(n, m); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ansb[i][j]) st.pb({U[i][j], L[i][j], D[i][j], R[i][j]}); sort(all(st)); return unique(all(st))-st.begin(); }

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

rect.cpp: In constructor 'node::node(int16_t, int16_t, int16_t)':
rect.cpp:37:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   if(l != r)L = new node(l, l+r>>1, m), R = new node((l+r>>1)+1, r, m);
      |                             ~^~
rect.cpp:37:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   if(l != r)L = new node(l, l+r>>1, m), R = new node((l+r>>1)+1, r, m);
      |                                                       ~^~
rect.cpp: In member function 'void node::answer(const std::vector<short int>&, std::function<bool(short int, short int)>)':
rect.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 0; i < v.size(); i++){
      |                  ~~^~~~~~~~~~
rect.cpp: In member function 'void node::process(std::vector<std::vector<short int> >&, std::function<bool(short int, short int)>)':
rect.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int i = 0; i < v[l].size(); i++)
      |                   ~~^~~~~~~~~~~~~
rect.cpp:59:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     v[l][i] = cmp(v[l][i], v[(l+r>>1)+1][i])?v[l][i]:v[(l+r>>1)+1][i];
      |                               ~^~
rect.cpp:59:58: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     v[l][i] = cmp(v[l][i], v[(l+r>>1)+1][i])?v[l][i]:v[(l+r>>1)+1][i];
      |                                                         ~^~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:106:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  106 |  for(auto& i: ans)fill(all(i), -2); t = U, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false;
      |  ^~~
rect.cpp:106:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  106 |  for(auto& i: ans)fill(all(i), -2); t = U, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false;
      |                                     ^
rect.cpp:107:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  107 |  for(auto& i: ans)fill(all(i), -2); t = L, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false;
      |  ^~~
rect.cpp:107:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  107 |  for(auto& i: ans)fill(all(i), -2); t = L, rt->process(t, [](int a, int b){ return a < b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false;
      |                                     ^
rect.cpp:108:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  108 |  for(auto& i: ans)fill(all(i), -2); t = D, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false;
      |  ^~~
rect.cpp:108:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |  for(auto& i: ans)fill(all(i), -2); t = D, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false;
      |                                     ^
rect.cpp:109:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  109 |  for(auto& i: ans)fill(all(i), -2); t = R, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false;
      |  ^~~
rect.cpp:109:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  109 |  for(auto& i: ans)fill(all(i), -2); t = R, rt->process(t, [](int a, int b){ return a > b; }); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false;
      |                                     ^
#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...