Submission #1094648

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1094648	2024-09-30T08:14:27 Z	razivo	Event Hopping (BOI22_events)	C++14	Compilation error	0 ms	0 KB

events

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
    int N,Q;
    cin>>N>>Q;
    vector<pair<int,int>> events;
    vector<pair<pair<int,int>,int>> u;
    for (int i = 0; i < N; ++i) {
        int x,y;
        cin>>x>>y;
        events.emplace_back(x,y);
        u.emplace_back(make_pair(x,0),i);
        u.emplace_back(make_pair(y,1),i);
    }
    sort(u.begin(),u.end());
    vector<vector<int>> lift(N);
    set<pair<int,int>> s;
    for (int i = 0; i < 2*N; ++i) {
        auto [a,j] = u[i];
        if(events[j].first==a.first) {
            s.insert({-events[j].second,j});
        }else {
            s.erase({-events[j].second,j});
            auto t = s.lower_bound({-INT_MAX,0});
            if(t!=s.end()) {
                lift[j].push_back(t->second);
            }else lift[j].push_back(j);
        }
    }
    int pos = 0;
    for(int i = 1; i<N; i*=2) {
        for (int j = 0; j < N; ++j) {
            if(pos<lift[j].size()&&pos<lift[lift[j][pos]].size()) {
                lift[j].push_back(lift[lift[j][pos]][pos]);
            }
        }
        pos++;
    }
    for (int i = 0; i < Q; ++i) {
        int s,e;
        cin>>s>>e; s--; e--;
        int ans = 0;
        bool t = true;
        while(s!=e) {
            if(events[e].first<=events[s].second&&events[s].second<=events[e].second) {
                ans++;
                break;
            }
            if(events[lift[s][0]].second>events[e].second) {
                cout<<"impossible"<<endl;
                s=e;
                t= false;
                continue;
            }
            int j = 1;
            int u = 1;
            while(j<lift[s].size()&&events[lift[s][j]].second<events[e].second){ j++; u*=2;}
            ans+=u;
            j--;
            if(s==lift[s][j]) {
                cout<<"impossible"<<endl;
                s=e;
                t= false;
                continue;
            }
            s= lift[s][j];
        }
        if(t) cout<<ans<<endl;
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:18:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   18 |     sort(u.begin(),u.end());
      |     ^~~~
      |     qsort
events.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |         auto [a,j] = u[i];
      |              ^
events.cpp:27:38: error: 'INT_MAX' was not declared in this scope
   27 |             auto t = s.lower_bound({-INT_MAX,0});
      |                                      ^~~~~~~
events.cpp:4:1: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    3 | #include <vector>
  +++ |+#include <climits>
    4 | using namespace std;
events.cpp:27:48: error: no matching function for call to 'std::set<std::pair<int, int> >::lower_bound(<brace-enclosed initializer list>)'
   27 |             auto t = s.lower_bound({-INT_MAX,0});
      |                                                ^
In file included from /usr/include/c++/10/set:61,
                 from events.cpp:2:
/usr/include/c++/10/bits/stl_set.h:829:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  829 |       lower_bound(const key_type& __x)
      |       ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:829:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
  829 |       lower_bound(const key_type& __x)
      |                   ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:833:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::const_iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) const [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  833 |       lower_bound(const key_type& __x) const
      |       ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:833:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
  833 |       lower_bound(const key_type& __x) const
      |                   ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:839:2: note: candidate: 'template<class _Kt> decltype ((std::set<_Key, _Compare, _Alloc>::iterator)(((std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_lower_bound_tr(__x))) std::set<_Key, _Compare, _Alloc>::lower_bound(const _Kt&) [with _Kt = _Kt; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  839 |  lower_bound(const _Kt& __x)
      |  ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:839:2: note:   template argument deduction/substitution failed:
events.cpp:27:48: note:   couldn't deduce template parameter '_Kt'
   27 |             auto t = s.lower_bound({-INT_MAX,0});
      |                                                ^
In file included from /usr/include/c++/10/set:61,
                 from events.cpp:2:
/usr/include/c++/10/bits/stl_set.h:845:2: note: candidate: 'template<class _Kt> decltype ((std::set<_Key, _Compare, _Alloc>::const_iterator)(((const std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_lower_bound_tr(__x))) std::set<_Key, _Compare, _Alloc>::lower_bound(const _Kt&) const [with _Kt = _Kt; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  845 |  lower_bound(const _Kt& __x) const
      |  ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:845:2: note:   template argument deduction/substitution failed:
events.cpp:27:48: note:   couldn't deduce template parameter '_Kt'
   27 |             auto t = s.lower_bound({-INT_MAX,0});
      |                                                ^
events.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             if(pos<lift[j].size()&&pos<lift[lift[j][pos]].size()) {
      |                ~~~^~~~~~~~~~~~~~~
events.cpp:36:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             if(pos<lift[j].size()&&pos<lift[lift[j][pos]].size()) {
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             while(j<lift[s].size()&&events[lift[s][j]].second<events[e].second){ j++; u*=2;}
      |                   ~^~~~~~~~~~~~~~~