제출 #1346983

#제출 시각아이디문제언어결과실행 시간메모리
1346983KindaGoodGamesEvent Hopping (BOI22_events)C++20
컴파일 에러
0 ms0 KiB
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include<bits/stdc++.h>


#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;

int INF = numeric_limits<int>::max()/2;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin >> n >> q;

    vector<pii>arr(n);
    vector<tiii>carr(n);

    for(int i = 0; i < n; i++){
        int a,b;
        cin >> a >>b;
        arr[i] = {a,b};
        carr[i] = {a,b,i};
    }

    sort(carr.begin(),carr.end(), [](tiii a, tiii b){return get<1>(a) < get<1>(b);});
    sort(carr.begin(),carr.end(), [](pii a, pii b){return a.first < b.second;});
    vector<int> newInd(n);
    for(int i = 0; i < n; i++){
        newInd[get<2>(carr[i])] = i;
    } 

    vector<vector<int>> ans(n,vector<int>(n,INF));

    for(int i = n-1; i >= 0; i--){
        int pt = n; 
        set<pii> cur;
        priority_queue<tiii> active;
        cur.insert({0,i});
        active.push({get<0>(arr[i]),i,0});
        ans[i][i] = 0;

        while(--pt >= 0){
            if(pt == i) continue;
            if(get<1>(arr[pt]) > get<1>(arr[i])) continue;
            while(active.size() && get<0>(active.top()) > get<1>(arr[pt])){
                int st, c, ind;
                tie(st, ind,c) = active.top(); active.pop();
                cur.erase({c,ind});
            }

            if(cur.size()) ans[pt][i] = (*cur.begin()).first+1;
            else break;

            cur.insert({ans[pt][i], pt});
            active.push({get<0>(arr[pt]), pt, ans[pt][i]});
        }
    }

    while(q--){
        int s,t;
        cin >> s >> t;
        s--;t--;
        s = newInd[s];
        t = newInd[t];

        if(ans[s][t] >= INF){
            cout << "impossible\n";
            continue;
        }else{
            cout << ans[s][t] << "\n";
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/13/bits/stl_algobase.h:71,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from events.cpp:2:
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::tuple<int, int, int>*, std::vector<std::tuple<int, int, int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::tuple<int, int, int>*, std::vector<std::tuple<int, int, int> > >; _Compare = main()::<lambda(std::pair<int, int>, std::pair<int, int>)>]':
/usr/include/c++/13/bits/stl_algo.h:1819:14:   required from 'constexpr void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1859:25:   required from 'constexpr void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1950:31:   required from 'constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:4894:18:   required from 'constexpr void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = main()::<lambda(pair<int, int>, pair<int, int>)>]'
events.cpp:30:9:   required from here
/usr/include/c++/13/bits/predefined_ops.h:158:30: error: no match for call to '(main()::<lambda(std::pair<int, int>, std::pair<int, int>)>) (std::tuple<int, int, int>&, std::tuple<int, int, int>&)'
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/predefined_ops.h:158:30: note: candidate: 'bool (*)(std::pair<int, int>, std::pair<int, int>)' (conversion)
/usr/include/c++/13/bits/predefined_ops.h:158:30: note:   candidate expects 3 arguments, 3 provided
events.cpp:30:35: note: candidate: 'main()::<lambda(std::pair<int, int>, std::pair<int, int>)>'
   30 |     sort(carr.begin(),carr.end(), [](pii a, pii b){return a.first < b.second;});
      |                                   ^
events.cpp:30:35: note:   no known conversion for argument 1 from 'std::tuple<int, int, int>' to 'std::pair<int, int>'
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::tuple<int, int, int>; _Iterator = __gnu_cxx::__normal_iterator<std::tuple<int, int, int>*, std::vector<std::tuple<int, int, int> > >; _Compare = main()::<lambda(std::pair<int, int>, std::pair<int, int>)>]':
/usr/include/c++/13/bits/stl_algo.h:1799:20:   required from 'constexpr void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1827:36:   required from 'constexpr void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1859:25:   required from 'constexpr void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1950:31:   required from 'constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:4894:18:   required from 'constexpr void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = main()::<lambda(pair<int, int>, pair<int, int>)>]'
events.cpp:30:9:   required from here
/usr/include/c++/13/bits/predefined_ops.h:240:30: error: no match for call to '(main()::<lambda(std::pair<int, int>, std::pair<int, int>)>) (std::tuple<int, int, int>&, std::tuple<int, int, int>&)'
  240 |         { return bool(_M_comp(__val, *__it)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/predefined_ops.h:240:30: note: candidate: 'bool (*)(std::pair<int, int>, std::pair<int, int>)' (conversion)
/usr/include/c++/13/bits/predefined_ops.h:240:30: note:   candidate expects 3 arguments, 3 provided
events.cpp:30:35: note: candidate: 'main()::<lambda(std::pair<int, int>, std::pair<int, int>)>'
   30 |     sort(carr.begin(),carr.end(), [](pii a, pii b){return a.first < b.second;});
      |                                   ^
events.cpp:30:35: note:   no known conversion for argument 1 from 'std::tuple<int, int, int>' to 'std::pair<int, int>'
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::tuple<int, int, int>*, std::vector<std::tuple<int, int, int> > >; _Value = std::tuple<int, int, int>; _Compare = main()::<lambda(std::pair<int, int>, std::pair<int, int>)>]':
/usr/include/c++/13/bits/stl_heap.h:140:48:   required from 'constexpr void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Distance = long int; _Tp = tuple<int, int, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_heap.h:247:23:   required from 'constexpr void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Distance = long int; _Tp = tuple<int, int, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_heap.h:356:22:   required from 'constexpr void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1635:23:   required from 'constexpr void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1910:25:   required from 'constexpr void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1926:27:   required from 'constexpr void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:1947:25:   required from 'constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(pair<int, int>, pair<int, int>)> >]'
/usr/include/c++/13/bits/stl_algo.h:4894:18:   required from 'constexpr void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<tuple<int, int, int>*, vector<tuple<int, int, int> > >; _Compare = main()::<lambda(pair<int, int>, pair<int, int>)>]'
events.cpp:30:9:   required from here
/usr/include/c++/13/bits/predefined_ops.h:196:30: error: no match for call to '(main()::<lambda(std::pair<int, int>, std::pair<int, int>)>) (std::tuple<int, int, int>&, std::tuple<int, int, int>&)'
  196 |         { return bool(_M_comp(*__it, __val)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/predefined_ops.h:196:30: note: candidate: 'bool (*)(std::pair<int, int>, std::pair<int, int>)' (conversion)
/usr/include/c++/13/bits/predefined_ops.h:196:30: note:   candidate expects 3 arguments, 3 provided
events.cpp:30:35: note: candidate: 'main()::<lambda(std::pair<int, int>, std::pair<int, int>)>'
   30 |     sort(carr.begin(),carr.end(), [](pii a, pii b){return a.first < b.second;});
      |                                   ^
events.cpp:30:35: note:   no known conversion for argument 1 from 'std::tuple<int, int, int>' to 'std::pair<int, int>'