제출 #653587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653587		AlperenT	Event Hopping (BOI22_events)	C++17	10 / 100	321 ms	524288 KiB

events

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5, INF = 1e9 + 5;

int n, q, canmove[N][N];

struct Event{
    int l, r;

    bool operator < (const Event &sc) const{
        if(r == sc.r) return l < sc.l;
        else return r < sc.r;
    }
};

Event arr[N];

vector<pair<Event, int>> v;

struct SegTree{
    int tree[N * 8];

    SegTree(){
        fill(tree, tree + N * 8, INF);
    }

    void reset(){
        fill(tree, tree + N * 8, INF);
    }

    int merge(int a, int b){
        return min(a, b);
    }

    int query(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
        if(l > r) return INF;
        else if(l == tl && r == tr) return tree[v];
        else{
            int tm = tl + (tr - tl) / 2;

            return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
        }
    }

    void update(int pos, int val, int v = 1, int l = 1, int r = N - 1){
        if(l == r) tree[v] = min(tree[v], val);
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update(pos, val, v * 2, l, m);
            else update(pos, val, v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }
};

SegTree sgt;

map<int, int> cmprs;

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

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            canmove[i][j] = INF;
        }
    }

    cin >> n >> q;

    for(int i = 1; i <= n; i++) cin >> arr[i].l >> arr[i].r;

    for(int i = 1; i <= n; i++) cmprs[arr[i].l] = cmprs[arr[i].r] = 1;

    int tmp = 0;

    for(auto &p : cmprs) p.second = ++tmp;

    for(int i = 1; i <= n; i++) arr[i].l = cmprs[arr[i].l], arr[i].r = cmprs[arr[i].r];

    for(int i = 1; i <= n; i++) v.push_back({arr[i], i});

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

    map<int, vector<int>> mp;

    for(int i = 1; i <= n; i++) mp[arr[i].r].push_back(i);

    for(auto p : mp){
        for(auto x : p.second){
            for(auto y : p.second){
                canmove[x][y] = 1;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        canmove[i][i] = 0;
    }

    for(int i = 1; i <= n; i++){
        sgt.reset();

        for(auto p : v){
            canmove[p.second][i] = min(canmove[p.second][i], sgt.query(p.first.l, p.first.r) + 1);

            sgt.update(p.first.r, canmove[p.second][i]);
        }
    }

    while(q--){
        int s, e;

        cin >> s >> e;

        if(canmove[e][s] == INF) cout << "impossible\n";
        else cout << canmove[e][s] << "\n"; 
    }
}

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