| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 396384 | peuch | 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;
const int MAXN = 5e5 + 10;
int n;
pair<int, int> v[MAXN];
int bank[MAXN];
int m;
int k[MAXN];
vector<int> seg, e, d;
int create();
int copia(int pos);
int update(int pos, int ini, int fim, int id);
int query(int pos, int ini, int fim, int p, int q);
void init(int N, int A[], int B[]) {
n = N;
create();
bank[0] = create();
for(int i = 0; i < n; i++)
v[i + 1] = make_pair(A[i], B[i]);
sort(v + 1, v + 1 + n);
for(int i = 1; i <= n; i++)
bank[i] = update(bank[i - 1], 1, n, v[i].second);
}
int can(int M, int K[]) {
m = M;
for(int i = 0; i < m; i++)
k[i + 1] = K[i];
sort(k + 1, k + 1 + m);
stack<pair<int, pair<int, int> > > pilha;
pilha.push(make_pair(MAXN + 10, make_pair(0, 0)));
for(int i = 1; i <= m; i++){
int j = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN + 10)) - v - 1;
if(j < 0) return 0;
while(k[i] > pilha.top().second) pilha.pop();
int sum = query(bank[j], 1, n, k[i], k[i]) - query(bank[pilha.top().second.first], 1, n, k[i], k[i]);
int hmin = k[i];
int hmax = k[i];
while(!pilha.empty()){
if(sum >= k[i]) break;
hmax = pilha.top().first;
int diff = query(bank[j], 1, n, hmin + 1, hmax) - query(bank[pilha.top().second.first], 1, n, hmin + 1, hmax);
if(diff + sum >= k[i]){
int ini = hmin + 1, fim = hmax;
while(ini != fim){
int mid = (ini + fim) >> 1;
diff = query(bank[j], 1, n, hmin + 1, mid) - query(bank[pilha.top().second.first], 1, n, hmin + 1, mid);
if(sum + diff >= k[i]) fim = mid;
else ini = mid + 1;
}
hmax = ini;
sum += diff;
break;
}
else sum += diff + pilha.top().second.second, hmin = hmax, pilha.pop();
}
if(sum < k[i]) return 0;
pilha.push(make_pair(hmax, make_pair(j, sum - k[i])));
}
return 1;
}
int create(){
seg.push_back(0);
e.push_back(0);
d.push_back(0);
return seg.size() - 1;
}
int copia(int pos){
seg.push_back(seg[pos]);
e.push_back(e[pos]);
d.push_back(d[pos]);
return seg.size() - 1;
}
int update(int pos, int ini, int fim, int id){
if(ini > id || fim < id) return pos;
int newNode = copia(pos);
if(ini == fim){
seg[newNode]++;
return newNode;
}
int mid = (ini + fim) >> 1;
int aux = update(e[pos], ini, mid, id);
e[newNode] = aux;
aux = update(d[pos], mid + 1, fim, id);
d[newNode] = aux;
seg[newNode] = seg[e[newNode]] + seg[d[newNode]];
return newNode;
}
int query(int pos, int ini, int fim, int p, int q){
if(ini > q || fim < p) return 0;
if(ini >= p && fim <= q) return seg[pos];
int mid = (ini + fim) >> 1;
return query(e[pos], ini, mid, p, q) + query(d[pos], mid + 1, fim, p, q);
}
Compilation message (stderr)
teams.cpp: In function 'int can(int, int*)':
teams.cpp:44:73: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
44 | int j = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN + 10)) - v - 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:47:14: error: no match for 'operator>' (operand types are 'int' and 'std::pair<int, int>')
47 | while(k[i] > pilha.top().second) pilha.pop();
| ~~~~ ^ ~~~~~~~~~~~~~~~~~~
| | |
| int std::pair<int, int>
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from teams.cpp:2:
/usr/include/c++/9/bits/regex.h:1081:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1081 | operator>(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1081:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from teams.cpp:2:
/usr/include/c++/9/bits/regex.h:1136: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>&)'
1136 | operator>(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1136:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from teams.cpp:2:
/usr/include/c++/9/bits/regex.h:1210: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>&)'
1210 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1210:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from teams.cpp:2:
/usr/include/c++/9/bits/regex.h:1284: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>&)'
1284 | operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1284:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from teams.cpp:2:
/usr/include/c++/9/bits/regex.h:1358: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*)'
1358 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1358:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from teams.cpp:2:
/usr/include/c++/9/bits/regex.h:1434: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>&)'
1434 | operator>(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1434:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from teams.cpp:2:
/usr/include/c++/9/bits/regex.h:1512: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&)'
1512 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1512:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from teams.cpp:2:
/usr/include/c++/9/bits/stl_pair.h:467:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator>(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
467 | operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:467:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::pair<_T1, _T2>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from teams.cpp:2:
/usr/include/c++/9/bits/stl_iterator.h:343:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
343 | operator>(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:343:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from teams.cpp:2:
/usr/include/c++/9/bits/stl_iterator.h:381:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
381 | operator>(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:381:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from teams.cpp:2:
/usr/include/c++/9/bits/stl_iterator.h:1187:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1187 | operator>(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1187:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from teams.cpp:2:
/usr/include/c++/9/bits/stl_iterator.h:1193:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1193 | operator>(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1193:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/bits/basic_string.h:48,
from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from teams.cpp:2:
/usr/include/c++/9/string_view:527:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
527 | operator> (basic_string_view<_CharT, _Traits> __x,
| ^~~~~~~~
/usr/include/c++/9/string_view:527:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/bits/basic_string.h:48,
from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from teams.cpp:2:
/usr/include/c++/9/string_view:533: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> >)'
533 | operator> (basic_string_view<_CharT, _Traits> __x,
| ^~~~~~~~
/usr/include/c++/9/string_view:533:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/bits/basic_string.h:48,
from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from teams.cpp:2:
/usr/include/c++/9/string_view:539: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>)'
539 | operator> (__detail::__idt<basic_string_view<_CharT, _Traits>> __x,
| ^~~~~~~~
/usr/include/c++/9/string_view:539:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: 'std::pair<int, int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from teams.cpp:2:
/usr/include/c++/9/bits/basic_string.h:6264: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>&)'
6264 | operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6264:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from teams.cpp:2:
/usr/include/c++/9/bits/basic_string.h:6277:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
6277 | operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6277:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from teams.cpp:2:
/usr/include/c++/9/bits/basic_string.h:6289:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6289 | operator>(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6289:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const _CharT*' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/tuple:39,
from /usr/include/c++/9/functional:54,
from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/9/algorithm:71,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from teams.cpp:2:
/usr/include/c++/9/array:270:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> bool std::operator>(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&)'
270 | operator>(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
| ^~~~~~~~
/usr/include/c++/9/array:270:5: note: template argument deduction/substitution failed:
teams.cpp:47:28: note: mismatched types 'const std::array<_Tp, _Nm>' and 'int'
47 | while(k[i] > pilha.top().second) pilha.pop();
| ^~~~~~
In file included from /usr/include/c++/9/functional:54,
from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/9/algorithm:71,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from /var/loca