Submission #298032

#TimeUsernameProblemLanguageResultExecution timeMemory
298032erd1Rectangles (IOI19_rect)C++14
Compilation error
0 ms0 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<int>> U, D, L, R; template<typename Cmp> struct Sgt{ Cmp _cmp; int cmp(int a, int b){ return _cmp(a, b)?a:b; } vector<vector<vector<int16_t>>> data; const vector<vector<int>>& v; int n, m; Sgt(const vector<vector<int>>& vv) : v(vv) { } void build_data(int j, int jj){ data[j].resize(__lg(m)+2); for(auto& i: data[j])i.resize(m); data[j][0] = v[jj]; for(int i = 1, c = 1; i < m; i <<= 1, c++){ for(int k = 0; k+i < m; k++) data[j][c][k] = cmp(data[j][c-1][k], data[j][c-1][k+i]); } } void build(int i, int ll, int rr){ if(data.size() <= i)data.resize(i+1); if(ll == rr) build_data(i, ll); else { build(i<<1, ll, (ll+rr)>>1); build((i<<1)+1, ((ll+rr)>>1)+1, rr); data[i] = data[i<<1]; for(int c = 0; c < __lg(m)+2; c++) for(int j = 0; j < m; j++) data[i][c][j] = cmp(data[i][c][j], data[(i<<1)+1][c][j]); } } void init(int nn, int mm){ n = nn, m = mm; build(1, 0, n-1); } int query_data(int j, int ql, int qr){ int d = __lg(qr-ql+1); return cmp(data[j][d][ql], data[j][d][qr-(1<<d)+1]); } int qquery(int i, int ll, int rr, int ql, int qr, int l2, int r2){ assert(ql <= rr && qr >= ll); if(ql <= ll && qr >= rr)return query_data(i, l2, r2); if(qr <= ((ll+rr)>>1))return qquery(i<<1, ll, (ll+rr)>>1, ql, qr, l2, r2); if(ql > ((ll+rr)>>1))return qquery((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr, l2, r2); return cmp(qquery(i<<1, ll, (ll+rr)>>1, ql, qr, l2, r2), qquery((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr, l2, r2)); } int query(int a, int b, int c, int d){ return qquery(1, 0, n-1, a, b, c, d); } }; /* template<typename Cmp> struct node{ node *L, *R; int l, r, mid, s; int cmp(int a, int b){ return Cmp()(a, b)?a:b; } vector<int> data; node(int ll, int rr, int st, const vector<vector<int>>& v) : l(ll), r(rr), mid((l+r)/2), s(st) { data.resize(s*4); if(l != r){ L = new node(l, mid, s, v), R = new node(mid+1, r, s, v); for(int i = 0; i < data.size(); i++)data.at(i) = cmp(L->data.at(i), R->data.at(i)); } else build_data(1, 0, s, v.at(l)); } void build_data(int i, int ll, int rr, const vector<int>& v){ if(data.size() <= i)data.resize(i+1); if(ll == rr)data[i] = v[ll]; else build_data(i<<1, ll, (ll+rr)>>1, v), build_data((i<<1)+1, ((ll+rr)>>1)+1, rr, v), data[i] = cmp(data[i<<1], data[(i<<1)+1]); } int query_data(int i, int ll, int rr, int ql, int qr){ //cout << ll << " " << rr << " " << ql << " " << qr << endl; assert(ql <= rr && qr >= ll); if(ql <= ll && qr >= rr)return data[i]; if(qr <= ((ll+rr)>>1))return query_data(i<<1, ll, (ll+rr)>>1, ql, qr); if(ql > ((ll+rr)>>1))return query_data((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr); return cmp(query_data(i<<1, ll, (ll+rr)>>1, ql, qr), query_data((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr)); } int query(int l1, int r1, int l2, int r2){ assert(l1 <= r && r1 >= l); if(l1 <= l && r1 >= r)return query_data(1, 0, s, l2, r2); if(l1 > mid)return R->query(l1, r1, l2, r2); if(r1 <= mid)return L->query(l1, r1, l2, r2); return cmp(L->query(l1, r1, l2, r2), R->query(l1, r1, l2, r2)); } }; */ Sgt<greater<int>> d(D), r(R); Sgt<less<int>> u(U), l(L); set<tuple<int, int, int, int>> st; long long count_rectangles(vector<vector<int>> a) { int n = a.size(), m = a[0].size(); U = D = L = R = a; 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}); } } 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(U[i][j] < 0 || D[i][j] >= n || L[i][j] < 0 || R[i][j] >= m)goto next; //cout << i << " " << j << " " << U[i][j] << D[i][j] << L[i][j] << R[i][j] << " " << u->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) << endl; if(u.query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != U[i][j])goto next; if(l.query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != L[i][j])goto next; if(d.query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != D[i][j])goto next; if(r.query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != R[i][j])goto next; st.insert({U[i][j], L[i][j], D[i][j], R[i][j]}); next:; } return st.size(); }

Compilation message (stderr)

rect.cpp: In instantiation of 'void Sgt<Cmp>::build(int, int, int) [with Cmp = std::less<int>]':
rect.cpp:57:3:   required from 'void Sgt<Cmp>::init(int, int) [with Cmp = std::less<int>]'
rect.cpp:149:13:   required from here
rect.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::vector<short int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |   if(data.size() <= i)data.resize(i+1);
      |      ~~~~~~~~~~~~^~~~
rect.cpp: In instantiation of 'void Sgt<Cmp>::build(int, int, int) [with Cmp = std::greater<int>]':
rect.cpp:57:3:   required from 'void Sgt<Cmp>::init(int, int) [with Cmp = std::greater<int>]'
rect.cpp:149:27:   required from here
rect.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::vector<short int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
rect.cpp: In instantiation of 'void Sgt<Cmp>::build_data(int, int) [with Cmp = std::less<int>]':
rect.cpp:46:16:   required from 'void Sgt<Cmp>::build(int, int, int) [with Cmp = std::less<int>]'
rect.cpp:57:3:   required from 'void Sgt<Cmp>::init(int, int) [with Cmp = std::less<int>]'
rect.cpp:149:13:   required from here
rect.cpp:38:14: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<short int> >, std::vector<short int> >::value_type' {aka 'std::vector<short int>'} and 'const value_type' {aka 'const std::vector<int>'})
   38 |   data[j][0] = v[jj];
In file included from /usr/include/c++/9/vector:72,
                 from rect.h:5,
                 from rect.cpp:1:
/usr/include/c++/9/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = short int; _Alloc = std::allocator<short int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'const value_type' {aka 'const std::vector<int>'} to 'const std::vector<short int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/9/vector:67,
                 from rect.h:5,
                 from rect.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:706:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = short int; _Alloc = std::allocator<short int>]'
  706 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:706:26: note:   no known conversion for argument 1 from 'const value_type' {aka 'const std::vector<int>'} to 'std::vector<short int>&&'
  706 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_vector.h:727:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = short int; _Alloc = std::allocator<short int>]'
  727 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:727:46: note:   no known conversion for argument 1 from 'const value_type' {aka 'const std::vector<int>'} to 'std::initializer_list<short int>'
  727 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
rect.cpp: In instantiation of 'void Sgt<Cmp>::build_data(int, int) [with Cmp = std::greater<int>]':
rect.cpp:46:16:   required from 'void Sgt<Cmp>::build(int, int, int) [with Cmp = std::greater<int>]'
rect.cpp:57:3:   required from 'void Sgt<Cmp>::init(int, int) [with Cmp = std::greater<int>]'
rect.cpp:149:27:   required from here
rect.cpp:38:14: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<short int> >, std::vector<short int> >::value_type' {aka 'std::vector<short int>'} and 'const value_type' {aka 'const std::vector<int>'})
   38 |   data[j][0] = v[jj];
In file included from /usr/include/c++/9/vector:72,
                 from rect.h:5,
                 from rect.cpp:1:
/usr/include/c++/9/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = short int; _Alloc = std::allocator<short int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'const value_type' {aka 'const std::vector<int>'} to 'const std::vector<short int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/9/vector:67,
                 from rect.h:5,
                 from rect.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:706:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = short int; _Alloc = std::allocator<short int>]'
  706 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:706:26: note:   no known conversion for argument 1 from 'const value_type' {aka 'const std::vector<int>'} to 'std::vector<short int>&&'
  706 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_vector.h:727:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = short int; _Alloc = std::allocator<short int>]'
  727 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:727:46: note:   no known conversion for argument 1 from 'const value_type' {aka 'const std::vector<int>'} to 'std::initializer_list<short int>'
  727 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~