Submission #809198

#	Time	Username	Problem	Language	Result	Execution time	Memory
809198		thimote75	Event Hopping (BOI22_events)	C++14	100 / 100	417 ms	37032 KiB

events

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string( pair<A, B> p ) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename T>
string to_string (T x) {
    string S = "[";
    bool first = true;
    for (const auto v : x) {
        if (!first) S += ", ";
        S += to_string(v);
        first = false;
    }
    S += "]";
    return S;
}
string to_string( string s) {
    return s;
}

void dbg_out () { cout << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cout << to_string(H) << " ";
    dbg_out(T...);
}

#ifdef TDEBUG
#  define dbg(...) { cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__); }
#else
#  define dbg(...)
#endif

using  Event = pair<int, int>;
using VEvent = vector<Event>;

using  Time = pair<pair<int, int>, pair<int, bool>>;
using VTime = vector<Time>;

using idata = vector<int>;
using igrid = vector<idata>;

struct CNT {
    set<pair<pair<int, int>, int>> m;

    void insert (int index, int left, int right) {
        while (m.size() != 0) {
            auto it = m.end(); it --;
            const auto data = *it;

            if (left <= data.first.second && data.first.first <= right)
                m.erase(data);
            else break ;
        }

        if (m.size() != 0) {
            auto it = m.end(); it --;
            const auto data = *it;

            if (right <= data.first.first && data.first.second <= left) return ;
        }

        m.insert({ {right, left}, index });
        dbg(index, left, right, m);
    }
    int query (int start) {
        dbg(start, m);
        auto it =m.lower_bound({{ start, -1 }, -1});
        if (it == m.end()) return -1;

        return (*it).second;
    }
};

const bool START = true;
const bool END   = false;

VEvent events;
VTime timings;

idata parent;
igrid parent_2k;
const int MAXK = 20;

void initBLF () {
    parent_2k.resize(parent.size(), idata(MAXK, -1));
    for (int i = 0; i < parent.size(); i ++)
        parent_2k[i][0] = parent[i];

    for (int k = 0; k + 1 < MAXK; k ++) {
        for (int i = 0; i < parent.size(); i ++) {
            if (parent_2k[i][k] == -1) continue ;

            parent_2k[i][k + 1] = parent_2k[parent_2k[i][k]][k];
        }
    }
}
pair<int, int> jump (int node, int finalEnd) {
    int count = 0;
    for (int k = MAXK - 1; k >= 0; k --) {
        int pot = parent_2k[node][k];
        if (pot == -1 || events[pot].first <= finalEnd) continue ;

        node = pot;
        count += 1 << k;
    }

    if (events[node].first <= finalEnd) return { node, 0 };

    return { parent[node], count + 1 };
}

map<int, int> compress (idata coordinates) {
    map<int, int> ans;
    set<int> h;
    for (int u : coordinates) h.insert(u);
    int i = 0;
    for (int u : h) ans.insert({ u, i ++ });
    return ans;
}

int main () {
    int N, Q;
    cin >> N >> Q;

    events.resize(N);

    idata coords;

    for (int i = 0; i < N; i ++) {
        int a, b;
        cin >> a >> b;

        events[i] = { a, b };

        coords.push_back(a);
        coords.push_back(b);
    }

    map<int, int> mC = compress(coords);

    for (int i = 0; i < N; i ++) {
        //events[i].first  = (*mC.find(events[i].first )).second;
        //events[i].second = (*mC.find(events[i].second)).second;

        timings.push_back({ { events[i].first,  events[i].first },  { i, START } });
        timings.push_back({ { events[i].second, events[i].first }, { i, END   } });
    }

    sort(timings.begin(), timings.end());

    CNT cnt;
    parent.resize(N);

    for (const auto &timing : timings) {
        int id = timing.second.first;
        bool F = timing.second.second;

        if (F == START) {

        } else {
            parent[id] = cnt.query( events[id].first );
            if (parent[id] != -1 && events[parent[id]].first >= events[id].first)
                parent[id] = -1;

            cnt.insert(id, events[id].first, events[id].second);
        }
    }  

    initBLF();

    for (int q = 0; q < Q; q ++) {
        int a, b;
        cin >> a >> b;
        a --;
        b --;

        if (a == b) {
            cout << "0\n";
            continue ;
        }
        if (events[a].second > events[b].second) {
            cout << "impossible\n";
            continue ;
        }

        pair<int, int> F = jump( b, events[a].second );
        
        if (F.first == -1) cout << "impossible\n";
        else cout << F.second + 1 << "\n";
    }
}

Compilation message (stderr)

events.cpp: In function 'void initBLF()':
events.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < parent.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
events.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for (int i = 0; i < parent.size(); i ++) {
      |                         ~~^~~~~~~~~~~~~~~

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