| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 115558 | WhipppedCream | Seats (IOI18_seats) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e6+5;
int r[maxn], c[maxn];
int n, m;
struct node
{
int mnr, mxr;
int mnc, mxc;
node(){}
node(int a, int b, int c, int d) : mnr(a), mxr(b), mnc(c), mxc(d) {}
bool operator == (node other) const
{
if(mnr != other.mnr) return false;
if(mnc != other.mnc) return false;
if(mxr != other.mxr) return false;
if(mxc != other.mxc) return false;
return true;
}
};
node st[4*maxn];
node pull(node &x, node &y)
{
return node(min(x.mnr, y.mnr), max(x.mxr, y.mxr), min(x.mnc, y.mnc), max(x.mxc, y.mxc));
}
void update(int x, int dr, int dc, int p = 1, int L = 0, int R = n*m-1)
{
if(L == R)
{
st[p] = node(dr, dr, dc, dc);
return;
}
int M = (L+R)/2;
if(x<= M) update(x, dr, dc, 2*p, L, M);
else update(x, dr, dc, 2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
node ask(int i, int j, int p = 1, int L = 0, int R = n*m-1)
{
if(i> R || j< L) return node(1e9, 0, 1e9, 0);
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
node x = ask(i, j, 2*p, L, M);
node y = ask(i, j, 2*p+1, M+1, R);
return pull(x, y);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n = H;
m = W;
for(int i = 0; i< n*m; i++)
{
r[i] = R[i]; c[i] = C[i];
update(i, r[i], c[i]);
}
}
int swap_seats(int a, int b)
{
update(a, r[b], c[b]);
update(b, r[a], c[a]);
swap(r[a], r[b]);
swap(c[a], c[b]);
int st = 0;
int ans = 0;
int cnt = 0;
while(st< n*m)
{
node x = ask(0, st);
int lo = st, hi = n*m-1;
if(ask(0, lo+1) != x) hi = lo;
while(lo< hi)
{
int mid = (lo+hi+1)/2;
node y = ask(0, mid);
if(x == y) lo = mid;
else hi = mid-1;
}
int sz = (x.mxr-x.mnr+1)*(x.mxc-x.mnc+1);
ans += st+1<= sz && sz<= lo+1;
st = lo+1;
cnt++;
}
// printf("incremented %d times\n", cnt);
return ans;
}
Compilation message (stderr)
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:85:19: error: no match for 'operator!=' (operand types are 'node' and 'node')
if(ask(0, lo+1) != x) hi = lo;
~~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from seats.cpp:1:
/usr/include/c++/7/bits/regex.h:951:5: note: candidate: template<class _BiIter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)
operator!=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
^~~~~~~~
/usr/include/c++/7/bits/regex.h:951:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from seats.cpp:1:
/usr/include/c++/7/bits/regex.h:1029:5: note: candidate: template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)
operator!=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/regex.h:1029:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from seats.cpp:1:
/usr/include/c++/7/bits/regex.h:1109:5: note: candidate: template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)
operator!=(const sub_match<_Bi_iter>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/regex.h:1109:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from seats.cpp:1:
/usr/include/c++/7/bits/regex.h:1186:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)
operator!=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
^~~~~~~~
/usr/include/c++/7/bits/regex.h:1186:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from seats.cpp:1:
/usr/include/c++/7/bits/regex.h:1260:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)
operator!=(const sub_match<_Bi_iter>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/regex.h:1260:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from seats.cpp:1:
/usr/include/c++/7/bits/regex.h:1337:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)
operator!=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/regex.h:1337:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from seats.cpp:1:
/usr/include/c++/7/bits/regex.h:1417:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)
operator!=(const sub_match<_Bi_iter>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/regex.h:1417:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from seats.cpp:1:
/usr/include/c++/7/bits/regex.h:1944:5: note: candidate: template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator!=(const std::__cxx11::match_results<_BiIter, _Alloc>&, const std::__cxx11::match_results<_BiIter, _Alloc>&)
operator!=(const match_results<_Bi_iter, _Alloc>& __m1,
^~~~~~~~
/usr/include/c++/7/bits/regex.h:1944:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
from /usr/include/c++/7/bits/specfun.h:45,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from seats.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:456:5: note: candidate: template<class _T1, class _T2> constexpr bool std::operator!=(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
^~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:456:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::pair<_T1, _T2>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/specfun.h:45,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from seats.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:311:5: note: candidate: template<class _Iterator> constexpr bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
operator!=(const reverse_iterator<_Iterator>& __x,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:311:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::reverse_iterator<_Iterator>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/specfun.h:45,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from seats.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:349:5: note: candidate: template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
operator!=(const reverse_iterator<_IteratorL>& __x,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:349:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::reverse_iterator<_Iterator>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/specfun.h:45,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from seats.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:1130:5: note: candidate: template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)
operator!=(const move_iterator<_IteratorL>& __x,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1130:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::move_iterator<_IteratorL>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/specfun.h:45,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from seats.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:1136:5: note: candidate: template<class _Iterator> constexpr bool std::operator!=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)
operator!=(const move_iterator<_Iterator>& __x,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1136:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::move_iterator<_IteratorL>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/iosfwd:40:0,
from /usr/include/c++/7/ios:38,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from seats.cpp:1:
/usr/include/c++/7/bits/postypes.h:221:5: note: candidate: template<class _StateT> bool std::operator!=(const std::fpos<_StateT>&, const std::fpos<_StateT>&)
operator!=(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
^~~~~~~~
/usr/include/c++/7/bits/postypes.h:221:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::fpos<_StateT>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/string:41:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from seats.cpp:1:
/usr/include/c++/7/bits/allocator.h:158:5: note: candidate: template<class _T1, class _T2> bool std::operator!=(const std::allocator<_CharT>&, const std::allocator<_T2>&)
operator!=(const allocator<_T1>&, const allocator<_T2>&)
^~~~~~~~
/usr/include/c++/7/bits/allocator.h:158:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::allocator<_CharT>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/string:41:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from seats.cpp:1:
/usr/include/c++/7/bits/allocator.h:164:5: note: candidate: template<class _Tp> bool std::operator!=(const std::allocator<_CharT>&, const std::allocator<_CharT>&)
operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
^~~~~~~~
/usr/include/c++/7/bits/allocator.h:164:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::allocator<_CharT>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/bits/basic_string.h:48:0,
from /usr/include/c++/7/string:52,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from seats.cpp:1:
/usr/include/c++/7/string_view:468:5: note: candidate: template<class _CharT, class _Traits> constexpr bool std::operator!=(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)
operator!=(basic_string_view<_CharT, _Traits> __x,
^~~~~~~~
/usr/include/c++/7/string_view:468:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'std::basic_string_view<_CharT, _Traits>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/bits/basic_string.h:48:0,
from /usr/include/c++/7/string:52,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from seats.cpp:1:
/usr/include/c++/7/string_view:474:5: note: candidate: template<class _CharT, class _Traits> constexpr bool std::operator!=(std::basic_string_view<_CharT, _Traits>, std::__detail::__idt<std::basic_string_view<_CharT, _Traits> >)
operator!=(basic_string_view<_CharT, _Traits> __x,
^~~~~~~~
/usr/include/c++/7/string_view:474:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'std::basic_string_view<_CharT, _Traits>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/bits/basic_string.h:48:0,
from /usr/include/c++/7/string:52,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from seats.cpp:1:
/usr/include/c++/7/string_view:480:5: note: candidate: template<class _CharT, class _Traits> constexpr bool std::operator!=(std::__detail::__idt<std::basic_string_view<_CharT, _Traits> >, std::basic_string_view<_CharT, _Traits>)
operator!=(__detail::__idt<basic_string_view<_CharT, _Traits>> __x,
^~~~~~~~
/usr/include/c++/7/string_view:480:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'std::basic_string_view<_CharT, _Traits>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from seats.cpp:1:
/usr/include/c++/7/bits/basic_string.h:6044:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:6044:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: 'node' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
if(ask(0, lo+1) != x) hi = lo;
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from seats.cpp:1:
/usr/include/c++/7/bits/basic_string.h:6057:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator!=(const _CharT* __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:6057:5: note: template argument deduction/substitution failed:
seats.cpp:85:22: note: mismatched types 'const _CharT*' and 'node'
if(ask(0, lo+1) != x) hi