| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 253103 | Hehehe | Roller Coaster Railroad (IOI16_railroad) | C++14 | 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> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "railroad.h"
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int H = 2e5 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);
//ifstream in(".in");
//ofstream out(".out");
ll n, m, p[H], siz[H];
ll pref[H];
struct edge{
ll ff, ss, w;
};
int find_set(int x){
if(x == p[x])return x;
return p[x] = find_set(p[x]);
}
void unionn(int x, int y){
x = find_set(x);
y = find_set(y);
if(x == y)return;
if(siz[x] < siz[y])swap(x, y);
p[y] = x;
siz[x] += siz[y];
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
n = (ll)sz(s);
ll ans = 0;
vector<ll>v;
for(int i = 0; i < n; i++){
v.push_back(s[i]);
v.push_back(t[i]);
}
sort(all(v));
v.resize(unique(all(v))-v.begin());
m = sz(v);
for(int i = 0; i <= m; i++){
p[i] = i;
pref[i] = 0;
siz[i] = 1;
}
pref[1] = -1;
for(int i = 0; i < n; i++){
s[i] = lower_bound(all(v), s[i]) - v.begin();
t[i] = lower_bound(all(v), t[i]) - v.begin();
pref[s[i]]++;
pref[t[i]]--;
unionn(s[i], t[i]);
}
vector<edge>edges;
for(int i = 0; i < m - 1; i++){
pref[i] += (i == 0 ? 0 : pref[i - 1]);
if(pref[i] != 0){
ans += max(0ll, pref[i])*(v[i + 1] - v[i]);
unionn(i, i + 1);
}
edges.push_back({i, i + 1, v[i + 1] - v[i]});
}
sort(all(edges));
for(auto it : edges){
if(find_set(it.ff) == find_set(it.ss))continue;
ans += it.w;
unionn(it.ff, it.ss);
}
return ans;
}
Compilation message (stderr)
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Iterator2 = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]':
/usr/include/c++/7/bits/stl_algo.h:81:17: required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1921:34: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1953:38: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1968:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:4836:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]'
railroad.cpp:98:20: required from here
/usr/include/c++/7/bits/predefined_ops.h:43:23: error: no match for 'operator<' (operand types are 'edge' and 'edge')
{ return *__it1 < *__it2; }
~~~~~~~^~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:43:23: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
{ return *__it1 < *__it2; }
~~~~~~~^~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:43:23: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
{ return *__it1 < *__it2; }
~~~~~~~^~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = edge; _Iterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]':
/usr/include/c++/7/bits/stl_algo.h:1828:20: required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1855:36: required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1885:25: required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1971:31: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:4836:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]'
railroad.cpp:98:20: required from here
/usr/include/c++/7/bits/predefined_ops.h:90:22: error: no match for 'operator<' (operand types are 'edge' and 'edge')
{ return __val < *__it; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:90:22: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
{ return __val < *__it; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:90:22: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
{ return __val < *__it; }
~~~~~~^~~~~~~
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Value = edge]':
/usr/include/c++/7/bits/stl_heap.h:133:48: required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Distance = long int; _Tp = edge; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/7/bits/stl_heap.h:237:23: required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Distance = long int; _Tp = edge; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_heap.h:342:22: required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1672:23: required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1933:25: required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1948:27: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1968:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:4836:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]'
railroad.cpp:98:20: required from here
/usr/include/c++/7/bits/predefined_ops.h:65:22: error: no match for 'operator<' (operand types are 'edge' and 'edge')
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
{ return *__it < __val; }
~~~~~~^~~~~~~