답안 #939631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939631 2024-03-06T15:40:31 Z haxorman 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
컴파일 오류
0 ms 0 KB
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int mxN = 150007;
const int SZ = 388;

ll n, l, step, pos[mxN], bkt[mxN], to[mxN], cnt[mxN];
vector<pair<ll,ll>> arr[SZ];

void fix(int b) {
    for (int i = arr[b].size()-1; i >= 0; --i) {
        int val = arr[b][i].first + l;
        auto it = upper_bound(arr[b].begin(), arr[b].end(),
                                              make_pair(val,LLONG_MAX));

        if (it == arr[b].end()) {
            to[arr[b][i].second] = val;
            cnt[arr[b][i].second] = 1;
        }
        else {
            to[arr[b][i].second] = to[(*it).second];
            cnt[arr[b][i].second] = cnt[(*it).second] + 1;
        }
    }
}

void construct() {
    for (int i = 0; i < n; ++i) {
        bkt[i] = i/SZ;
        arr[i/SZ].push_back({pos[i],i});
    }

    for (int b = 0; b < SZ; ++b) {
        sort(arr[b].begin(), arr[b].end());
        fix(b);
    }
}

void init(int N, int L, int X[]) {
    n = N, l = L;
    
    for (int i = 0; i < n; ++i) {
        pos[i] = X[i];
    }
    construct();
}

int update(int i, int y) {
    for (int j = 0; j < arr[bkt[i]].size(); ++j) {
        if (arr[bkt[i]][j].second == i) {
            arr[bkt[i]].erase(arr[bkt[i]].begin() + j);
            break;
        }
    }
    fix(bkt[i]);
    
    for (int b = 0; b < SZ; ++b) {
        if (b == SZ-1 || (arr[b].size() && arr[b].back().first > y)) {
            bkt[i] = b;
            arr[b].push_back({pos[i] = y, i});
            sort(arr[b].begin(), arr[b].end());
            
            fix(b);
            break;
        }
    }
    
    ll ans = 0, cur = -1;
    for (int b = 0; b < SZ; ++b) {
        if (arr[b].size() && arr[b].back().first > cur) {
            auto it = upper_bound(arr[b].begin(), arr[b].end(),
                                                  make_pair(cur,LLONG_MAX));

            ans += cnt[(*it).second];
            cur = to[(*it).second];
        }
    }

    step++;
    if (step == SZ) {
        construct();
        step = 0;
    }
    return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int j = 0; j < arr[bkt[i]].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = const std::pair<int, long long int>; _Iterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >]':
/usr/include/c++/10/bits/stl_algo.h:2061:14:   required from '_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Tp = std::pair<int, long long int>; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:2096:32:   required from '_FIter std::upper_bound(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Tp = std::pair<int, long long int>]'
elephants.cpp:17:71:   required from here
/usr/include/c++/10/bits/predefined_ops.h:96:22: error: no match for 'operator<' (operand types are 'const std::pair<int, long long int>' and 'std::pair<long long int, long long int>')
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1096: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>&)'
 1096 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, long long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1104: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>&)'
 1104 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, long long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1075:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1075 |     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1075:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1156: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>&)'
 1156 |     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1156:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, long long int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1249: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>&)'
 1249 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1249:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1323: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>&)'
 1323 |     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1323:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from elephants.cpp:2:
/usr/include/c++/10/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*)'
 1417 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1417:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1492: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>&)'
 1492 |     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1492:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1592: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&)'
 1592 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1592:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:489:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  489 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:489:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   deduced conflicting types for parameter '_T1' ('int' and 'long long int')
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:366:5: note: candidate: 'template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  366 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:366:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:404:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  404 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:404:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/1