| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 941979 | Edu175 | Aliens (IOI16_aliens) | C++17 | 컴파일 에러 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto messi:v)cout<<messi<<" "; cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define bint __int128
const ll INF=2e12;
ll sq(ll n){return n*n;}
vector<ii>a;
ll sup(ll i){
return (!i?0:sq(max(a[i-1].snd-a[i].fst,(ll)0)));
}
const ll MAXN=1e5+5;
ll dp[MAXN],cnt[MAXN];
//(min, increasing insert coefficents, non increasing queries, online)
//for maximum just change the sign of lines
ll idiv(ll a, ll b){ //int division
/*if((a<0)^(b<0))return (a+b-1)/b; //ceil
return a/b; //floor*/
return a/b+(a%b?!((a>0)^(b>0)):0); // ==ceil(a/b)
}
struct ln{
bint a,b,i;
bint eq(bint x){return a*x+b;}
pair<bint,bint> operator^(ln l){
bint x=idiv(b-l.b,l.a-a);
return {x,eq(x)};
}
};
deque<ln>cht;
ii query(bint x){
ln l=cht.back(); cht.pop_back();
while(SZ(cht)&&l.eq(x)>=cht.back().eq(x))l=cht.back(),cht.pop_back();
cht.pb(l);
return {cht.back().eq(x)/MAXN,cht.back().i};
}
void insert(ln l){
l.a*=MAXN,l.b=l.b*MAXN+cnt[l.i];
if(!SZ(cht)){
cht.pb(l);
return;
}
ln m=cht.front(); cht.pop_front();
while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
m=cht.front(),cht.pop_front();
cht.push_front(m), cht.push_front(l);
}
void f(ll n, ll d){
cht.clear();
//cout<<"f "<<d<<":\n";
for(ll i=n-1;i>=0;i--){
insert(ln({-2*a[i].snd,sq(a[i].snd)+dp[i+1],i+1}));
ll &res=dp[i];
ii rq=query(a[i].fst);
res=rq.fst+sq(a[i].fst)-sup(i)+d;
cnt[i]=cnt[rq.snd]+1;
//cout<<i<<": ("<<rq.snd<<") "<<dp[i]<<" "<<cnt[i]<<"\n";
}
//cout<<cnt[0]<<"\n\n";
}
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
vector<ii>a_;
fore(i,0,n){
ll l=R[i],r=C[i];
if(l>r)swap(l,r);
r++;
a.pb({l,-r});
}
sort(ALL(a));
//for(auto i:a)cout<<i.fst<<","<<i.snd<<" ";;cout<<"\n";;
ll r=0;
for(auto [s,e]:a){
e=-e;
if(e>r)a_.pb({s,e}),r=e;
}
a=a_;
n=SZ(a);
//for(auto i:a)cout<<i.fst<<","<<i.snd<<" ";;cout<<"\n";
ll l=0; r=1e13;
while(l<=r){
ll m=(l+r)/2;
f(n,m);
if(cnt[0]<=k)r=m-1;
else l=m+1;
}
//cout<<n<<" "<<k<<"\n";
//cout<<l<<"\n";
f(n,l);
ll res=dp[0]-l*k;
//cout<<cnt[0]<<"\n";
return res;
}컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'void insert(ln)':
aliens.cpp:55:52: error: no match for 'operator==' (operand types are 'ln' and 'ln')
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ~^~~
| | |
| ln ln
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from aliens.cpp:2:
/usr/include/c++/10/bits/regex.h:1035:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1035 | operator==(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1035:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from aliens.cpp:2:
/usr/include/c++/10/bits/regex.h:1131: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>&)'
1131 | operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1131:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from aliens.cpp:2:
/usr/include/c++/10/bits/regex.h:1206: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>&)'
1206 | operator==(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1206:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from aliens.cpp:2:
/usr/include/c++/10/bits/regex.h:1298: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>&)'
1298 | operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1298:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from aliens.cpp:2:
/usr/include/c++/10/bits/regex.h:1373: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*)'
1373 | operator==(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1373:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from aliens.cpp:2:
/usr/include/c++/10/bits/regex.h:1466: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>&)'
1466 | operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1466:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from aliens.cpp:2:
/usr/include/c++/10/bits/regex.h:1545: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&)'
1545 | operator==(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1545:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from aliens.cpp:2:
/usr/include/c++/10/bits/regex.h:2101: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>&)'
2101 | operator==(const match_results<_Bi_iter, _Alloc>& __m1,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:2101:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from aliens.h:3,
from aliens.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:466:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
466 | operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:466:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::pair<_T1, _T2>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from aliens.h:3,
from aliens.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:360:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
360 | operator==(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:360:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::reverse_iterator<_Iterator>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from aliens.h:3,
from aliens.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:398:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
398 | operator==(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:398:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::reverse_iterator<_Iterator>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from aliens.h:3,
from aliens.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1427 | operator==(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::move_iterator<_IteratorL>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from aliens.h:3,
from aliens.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1495 | operator==(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::move_iterator<_IteratorL>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/vector:64,
from aliens.h:3,
from aliens.cpp:1:
/usr/include/c++/10/bits/allocator.h:206:5: note: candidate: 'template<class _T1, class _T2> bool std::operator==(const std::allocator<_Tp1>&, const std::allocator<_T2>&)'
206 | operator==(const allocator<_T1>&, const allocator<_T2>&)
| ^~~~~~~~
/usr/include/c++/10/bits/allocator.h:206:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::allocator<_Tp1>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/vector:67,
from aliens.h:3,
from aliens.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1892:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator==(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)'
1892 | operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1892:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::vector<_Tp, _Alloc>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from aliens.cpp:2:
/usr/include/c++/10/bits/postypes.h:222:5: note: candidate: 'template<class _StateT> bool std::operator==(const std::fpos<_StateT>&, const std::fpos<_StateT>&)'
222 | operator==(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/postypes.h:222:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::fpos<_StateT>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
from /usr/include/c++/10/string:55,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from aliens.cpp:2:
/usr/include/c++/10/string_view:490:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator==(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
490 | operator==(basic_string_view<_CharT, _Traits> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:490:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'std::basic_string_view<_CharT, _Traits>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
from /usr/include/c++/10/string:55,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from aliens.cpp:2:
/usr/include/c++/10/string_view:496:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator==(std::basic_string_view<_CharT, _Traits>, std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >)'
496 | operator==(basic_string_view<_CharT, _Traits> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:496:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'std::basic_string_view<_CharT, _Traits>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
from /usr/include/c++/10/string:55,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from aliens.cpp:2:
/usr/include/c++/10/string_view:519:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator==(std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >, std::basic_string_view<_CharT, _Traits>)'
519 | operator==(__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:519:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'std::basic_string_view<_CharT, _Traits>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.front()))
| ^
In file included from /usr/include/c++/10/string:55,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from aliens.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6153:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator==(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6153 | operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6153:5: note: template argument deduction/substitution failed:
aliens.cpp:55:54: note: 'ln' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
55 | while(SZ(cht)&&((l^m).fst>(m^cht.front()).fst||l^m==m^cht.