# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1018060 | DorostWef | Teams (IOI15_teams) | 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 "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second
const int MXN = 500005, SegN = (1 << 20), LG = 19;
pii a[MXN];
int n;
vector <int> seg[SegN];
bitset <SegN> f;
int e[SegN], ans[SegN];
vector <int> vv;
int cnt (int v, int x) {
if (seg[v].empty())
return 0;
return (upper_bound (seg[v].begin(), seg[v].end(), x)) - (upper_bound (seg[v].begin(), seg[v].end(), e[v])) - ans[v];
}
void shift (int v) {
vv.push_back(v);
vv.push_back(v * 2);
vv.push_back(v * 2 + 1);
if (e[v] > e[v * 2]) {
e[v * 2] = e[v];
ans[v * 2] = 0;
}
if (e[v] > e[v * 2 + 1]) {
e[v * 2 + 1] = e[v];
ans[v * 2 + 1] = 0;
}
}
int find (int x) {
int k = x;
int v = (1 << LG) + (lower_bound (a, a + n, make_pair(x, 0)) - a);
while (true) {
while (v % 2 == 0)
v /= 2;
vector <int> wef;
int few = v;
while (few > 1) {
few /= 2;
wef.push_back(few);
}
reverse(wef.begin(), wef.end());
for (int ff : wef)
shift (ff);
int w = cnt(v, x);
if (w >= k) {
break;
} else {
if (f[v]) {
return MXN;
}
e[v] = x;
for (int ff : wef) {
ans[ff] += w;
}
ans[v] = 0;
k -= w;
v /= 2;
++v;
}
}
while (v < (1 << LG)) {
shift (v);
int w = (cnt (v * 2, x));
vector <int> wef;
int few = v;
while (few) {
wef.push_back(few);
few /= 2;
}
if (w >= k) {
v *= 2;
} else {
v *= 2;
e[v] = x;
for (int ff : wef)
ans[ff] += w;
ans[v] = 0;
v++;
k -= w;
}
}
vector <int> wef;
int few = v;
while (few > 1) {
few /= 2;
wef.push_back(few);
}
int w = 1;
e[v] = x;
for (int ff : wef)
ans[ff] += w;
ans[v] = 0;
return (v - (1 << LG));
}
void init(int N, int A[], int B[]) {
for (int i = 0; i <= 20; i++) {
f[(1 << i) - 1] = true;
}
n = N;
for (int i = 0; i < n; i++) {
a[i].F = B[i];
a[i].S = A[i];
}
sort (a, a + n);
for (int i = SegN - 1; i >= 0; i--) {
if (i >= (1 << LG)) {
if ((i - (1 << LG)) < n) {
seg[i].reserve(1);
seg[i].resize(1);
seg[i][i] = a[i - (1 << LG)].S;
}
} else {
seg[i].reserve((int)seg[i << 1].size() + (int)seg[i << 1 + 1].size());
seg[i].resize((int)seg[i << 1].size() + (int)seg[i << 1 + 1].size());
merge (seg[i << 1].begin(), seg[i << 1].end(), seg[i << 1 | 1].begin(), seg[i << 1 | 1].end(), seg[i]);
}
}
}
int can(int M, int K[]) {
vv.clear();
sort (K, K + M);
bool h = true;
int st = 0;
for (int i = 0; i < M; i++) {
st = find (K[i]);
if (st > n)
h = false;
else if (a[st].F < K[i])
h = false;
}
for (int v : vv) {
e[v] = 0;
ans[v] = 0;
}
return h;
}
Compilation message (stderr)
teams.cpp: In function 'int cnt(int, int)': teams.cpp:21:110: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion] 21 | return (upper_bound (seg[v].begin(), seg[v].end(), x)) - (upper_bound (seg[v].begin(), seg[v].end(), e[v])) - ans[v]; | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~ teams.cpp: In function 'int find(int)': teams.cpp:40:20: warning: conversion from 'long int' to 'int' may change value [-Wconversion] 40 | int v = (1 << LG) + (lower_bound (a, a + n, make_pair(x, 0)) - a); | ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ teams.cpp: In function 'void init(int, int*, int*)': teams.cpp:123:61: warning: suggest parentheses around '+' inside '<<' [-Wparentheses] 123 | seg[i].reserve((int)seg[i << 1].size() + (int)seg[i << 1 + 1].size()); | ~~^~~ teams.cpp:124:60: warning: suggest parentheses around '+' inside '<<' [-Wparentheses] 124 | seg[i].resize((int)seg[i << 1].size() + (int)seg[i << 1 + 1].size()); | ~~^~~ In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h: In instantiation of '_OutputIterator std::__merge(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _OutputIterator, _Compare) [with _InputIterator1 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _InputIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _OutputIterator = std::vector<int>; _Compare = __gnu_cxx::__ops::_Iter_less_iter]': /usr/include/c++/10/bits/stl_algo.h:4963:37: required from '_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter) [with _IIter1 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _IIter2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _OIter = std::vector<int>]' teams.cpp:125:105: required from here /usr/include/c++/10/bits/stl_algo.h:4907:8: error: no match for 'operator*' (operand type is 'std::vector<int>') 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/c++/10/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54, from teams.cpp:2: /usr/include/c++/10/complex:391:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const std::complex<_Tp>&)' 391 | operator*(const complex<_Tp>& __x, const complex<_Tp>& __y) | ^~~~~~~~ /usr/include/c++/10/complex:391:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: 'std::vector<int>' is not derived from 'const std::complex<_Tp>' 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/c++/10/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54, from teams.cpp:2: /usr/include/c++/10/complex:400:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const _Tp&)' 400 | operator*(const complex<_Tp>& __x, const _Tp& __y) | ^~~~~~~~ /usr/include/c++/10/complex:400:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: 'std::vector<int>' is not derived from 'const std::complex<_Tp>' 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/c++/10/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54, from teams.cpp:2: /usr/include/c++/10/complex:409:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const _Tp&, const std::complex<_Tp>&)' 409 | operator*(const _Tp& __x, const complex<_Tp>& __y) | ^~~~~~~~ /usr/include/c++/10/complex:409:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: candidate expects 2 arguments, 1 provided 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/c++/10/valarray:603, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)' 407 | _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/valarray_after.h:407:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: 'std::vector<int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>' 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/c++/10/valarray:603, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)' 407 | _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/valarray_after.h:407:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: 'std::vector<int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>' 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/c++/10/valarray:603, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)' 407 | _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/valarray_after.h:407:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: candidate expects 2 arguments, 1 provided 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/c++/10/valarray:603, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)' 407 | _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/valarray_after.h:407:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: 'std::vector<int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>' 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/c++/10/valarray:603, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)' 407 | _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/valarray_after.h:407:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: candidate expects 2 arguments, 1 provided 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const std::valarray<_Tp>&)' 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/valarray:1187:1: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: 'std::vector<int>' is not derived from 'const std::valarray<_Tp>' 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const typename std::valarray<_Tp>::value_type&)' 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/valarray:1187:1: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: 'std::vector<int>' is not derived from 'const std::valarray<_Tp>' 4907 | *__result = *__first2; | ^~~~~~~~~ In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const typename std::valarray<_Tp>::value_type&, const std::valarray<_Tp>&)' 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/valarray:1187:1: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4907:8: note: candidate expects 2 arguments, 1 provided 4907 | *__result = *__first2; | ^~~~~~~~~ /usr/include/c++/10/bits/stl_algo.h:4912:8: error: no match for 'operator*' (operand type is 'std::vector<int>') 4912 | *__result = *__first1; | ^~~~~~~~~ In file included from /usr/include/c++/10/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54, from teams.cpp:2: /usr/include/c++/10/complex:391:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const std::complex<_Tp>&)' 391 | operator*(const complex<_Tp>& __x, const complex<_Tp>& __y) | ^~~~~~~~ /usr/include/c++/10/complex:391:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4912:8: note: 'std::vector<int>' is not derived from 'const std::complex<_Tp>' 4912 | *__result = *__first1; | ^~~~~~~~~ In file included from /usr/include/c++/10/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54, from teams.cpp:2: /usr/include/c++/10/complex:400:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const _Tp&)' 400 | operator*(const complex<_Tp>& __x, const _Tp& __y) | ^~~~~~~~ /usr/include/c++/10/complex:400:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4912:8: note: 'std::vector<int>' is not derived from 'const std::complex<_Tp>' 4912 | *__result = *__first1; | ^~~~~~~~~ In file included from /usr/include/c++/10/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54, from teams.cpp:2: /usr/include/c++/10/complex:409:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const _Tp&, const std::complex<_Tp>&)' 409 | operator*(const _Tp& __x, const complex<_Tp>& __y) | ^~~~~~~~ /usr/include/c++/10/complex:409:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4912:8: note: candidate expects 2 arguments, 1 provided 4912 | *__result = *__first1; | ^~~~~~~~~ In file included from /usr/include/c++/10/valarray:603, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)' 407 | _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/valarray_after.h:407:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4912:8: note: 'std::vector<int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>' 4912 | *__result = *__first1; | ^~~~~~~~~ In file included from /usr/include/c++/10/valarray:603, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)' 407 | _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/valarray_after.h:407:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from teams.cpp:2: /usr/include/c++/10/bits/stl_algo.h:4912:8: note: 'std::vector<int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>' 4912 | *__result = *__first1; | ^~~~~~~~~ In file included from /usr/include/c++/10/valarray:603, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95, from teams.cpp:2: /usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::_