Submission #1094650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094650		razivo	Event Hopping (BOI22_events)	C++14	30 / 100	335 ms	24536 KiB

events

#include <iostream>
#include <climits>
#include <algorithm>
#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 (stderr)

events.cpp: In function 'int main()':
events.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         auto [a,j] = u[i];
      |              ^
events.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(pos<lift[j].size()&&pos<lift[lift[j][pos]].size()) {
      |                ~~~^~~~~~~~~~~~~~~
events.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(pos<lift[j].size()&&pos<lift[lift[j][pos]].size()) {
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             while(j<lift[s].size()&&events[lift[s][j]].second<events[e].second){ j++; u*=2;}
      |                   ~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30