Submission #718036

#	Time	Username	Problem	Language	Result	Execution time	Memory
718036		fatemetmhr	Event Hopping (BOI22_events)	C++17	100 / 100	434 ms	37432 KiB

events

// Be name khoda //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair

const int maxn5 = 2e5 + 10;
const int lg    = 19;

vector <int> ch, av, req[maxn5];
int l[maxn5], r[maxn5], ans[maxn5], par[lg][maxn5];
int x[maxn5], y[maxn5], ind[maxn5], per[maxn5];
pair <int, int> fen[maxn5];


inline bool cmp(int i, int j){return r[i] < r[j] || (r[i] == r[j] && l[i] < l[j]);}

inline void max_mos(int id, pair <int, int> val){
    for(++id; id < maxn5; id += id & -id){
        fen[id] = max(fen[id], val);
        ch.pb(id);
    }
}

inline pair <int, int> get_max(int id){
    pair <int, int> ret = {-1, -1};
    for(++id; id; id -= id & -id)
        ret = max(ret, fen[id]);
    return ret;
}

inline void fen_reset(){
    for(auto u : ch)
        fen[u] = {-1, -1};
    ch.clear();
}

void solve(int lq, int rq){
    if(rq - lq == 1)
        return;
    int mid = (lq + rq) >> 1;
    solve(lq, mid);
    int mn = l[per[mid]];
    for(int i = mid; i < rq; i++){ 
        mn = min(mn, l[per[i]]);
        max_mos(l[per[i]], mp(r[per[i]], i));
        for(auto id : req[i]) if(x[id] >= lq && x[id] < mid){
            int v = x[id];
            if(r[per[v]] < mn){
                for(int j = lg - 1; j >= 0; j--) if(par[j][v] != -1 && r[per[par[j][v]]] < mn){
                    v = par[j][v];
                    ans[id] += (1 << j);
                }
                v = par[0][v];
                ans[id]++;
            }
            if(v == -1){
                ans[id] = -1;
                continue;
            }
            //cout << "hey it's " << i << ' ' << id << ' ' << x[id] << ' ' << v << '\n';
            auto mx = get_max(r[per[v]]);
            x[id] = mx.se;
            ans[id]++;
        }
    }
    for(int i = mid - 1; i >= lq; i--){
        for(int j = 0; j < lg; j++)
            par[j][i] = -1;
        par[0][i] = get_max(r[per[i]]).se;
        max_mos(l[per[i]], mp(r[per[i]], i));
    }
    fen_reset();
    solve(mid, rq);
    for(int i = 1; i < lg; i++) for(int v = lq; v < mid; v++)
        if(par[i - 1][v] != -1) par[i][v] = par[i - 1][par[i - 1][v]];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    fill(fen, fen + maxn5, mp(-1, -1));

    int n, q; cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> l[i] >> r[i];
        av.pb(l[i]);
        av.pb(r[i]);
        per[i] = i;
    }
    sort(all(av));
    av.resize(unique(all(av)) - av.begin());
    for(int i = 0; i < n; i++){
        l[i] = lower_bound(all(av), l[i]) - av.begin();
        r[i] = lower_bound(all(av), r[i]) - av.begin();
        //cout << i << ' ' << l[i] << ' ' << r[i] << '\n';
    }
    sort(per, per + n, cmp);
    for(int i = 0; i < n; i++)
        ind[per[i]] = i;

    for(int i = 0; i < q; i++){
        cin >> x[i] >> y[i];
        x[i]--; y[i]--;
        if(x[i] == y[i])
            continue;
        if(ind[x[i]] > ind[y[i]])
            ans[i] = r[y[i]] == r[x[i]] ? 1 : -1;
        else{
            req[ind[y[i]]].pb(i);
            x[i] = ind[x[i]];
            y[i] = ind[y[i]];
        }
        //cout << "ok " << i << ' ' << x[i] << ' ' << y[i] << '\n';
    }

    memset(par, -1, sizeof par);

    solve(0, n);
    for(int i = 0; i < q; i++){
        if(ans[i] == -1)
            cout << "impossible\n";
        else
            cout << ans[i] << '\n';
    }
}

/*
5 1
1 3
2 4
4 7
7 9
3 7
1 4

3 2
*/

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