oj.uz

답안 #721904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721904 2023-04-11T08:41:01 Z drdilyor Event Hopping (BOI22_events) C++17
20 / 100
 595 ms 27616 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
 
const int inf = 1e9 + 1e5;
struct event {
    int l, r, i;
};

struct segtree {
    int n;
    vector<pair<int,int>> t;
    segtree(int n) : n(n), t(n*4, {-1, -1}) {}
    void update(int i, const pair<int,int>& x) {
        t[i+=n] = x;
        for (i /= 2; i >= 1; i/= 2) {
            t[i] = max(t[i*2], t[i*2+1]);
        }
    }
    pair<int,int> query(int l, int r) {
        l += n;
        r += n;
        pair<int,int> res{-1,-1};
        while (l <= r) {
            if (l%2==1) res = max(res, t[l++]);
            if (r%2==0) res = max(res, t[r--]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

int subtask_5(int n, int m, int k, vector<event>& ev, vector<event>& og)  {
    segtree mxr(k);

    for (int i = 0; i < n;i ++) {
        mxr.update(ev[i].l, {ev[i].r, i});
    }

    vector jmp(20, vector(n, -1));
    for (int i = 0; i < n; i++) {
        pair<int,int> mx = mxr.query(0, ev[i].r);
        if (mx.first != ev[i].r)
            jmp[0][i] = mx.second;
    }
    for (int j = 1; j < 20; j++)
        for (int i = 0; i < n;i++)
            if (jmp[j-1][i] != -1)
                jmp[j][i] = jmp[j-1][jmp[j-1][i]];

    vector<int> iof(n);
    for (int i = 0; i < n; i++)
        iof[ev[i].i] = i;


    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
 
        if (s == e) {
            cout << "0\n";
            continue;
        }
        if (og[e].l <= og[s].r && og[s].r <= og[e].r) {
            cout << "1\n";
            continue;
        }
        if (og[e].r < og[s].r) {
            cout << "impossible\n";
            continue;
        }

        int si = iof[s], ei = iof[e];
 
        int res = 0;
        for (int j = 19; j >= 0; j--) {
            if (jmp[j][si] != -1 && ev[jmp[j][si]].r < ev[ei].l) {
                si = jmp[j][si];
                res += 1<<j;
            }
        }
        int j = jmp[0][si];
        if (j != -1 && jmp[0][j] != -1 && ev[ei].l <= ev[jmp[0][j]].r) {
            cout << res+2 << '\n';
        } else {
            cout << "impossible\n";
        }
    }
 
    return 0;
}

int subtask_4(int n, int m, int k, vector<event>& ev, vector<event>& og)  {
 
 
    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
 
        if (s == e) {
            cout << "0\n";
            continue;
        }
 
 
        int si = 0, ei = 0;
        for (int j = 0; j < n; j++) {
            if (ev[j].i == s) si = j;
            if (ev[j].i == e) ei = j;
        }
 
        int res = 0;
        bool found = 0;
        int left = ev[ei].l;
        set<int> st;
        for (int j = n-1; j >= 0; j--) {
            auto [l,r,_i] = ev[j];
            if (r > ev[ei].r) continue;
            if (r < left) {
                if (st.empty()) break;
                left = *st.begin();
                if (r < left) break;
                st.clear();
                res++;
            }
            if (j == si) {
                res++;
                found = 1;
                break;
            }
            st.insert(l);
            continue;
        }
 
 
        if (found) cout << res << '\n';
        else cout << "impossible\n";
    }
 
    return 0;
}

int subtask_3(int n, int m, int k, vector<event>& ev, vector<event>& og) {
    vector ans(n, vector(n, inf));
    vector<int> mnl(k, inf);
    for (auto [l, r, i] :ev) {
        mnl[r] = min(mnl[r], l);
    }
 
    for (int ei = n-1; ei >= 0; ei--) {
        int res = 0;
        int lb = ev[ei].l, rb = ev[ei].r;
        for (int j = n-1; j >= 0; j--) {
            auto [l,r,_i] = ev[j];
            if (r > ev[ei].r) continue;
            if (r < lb) {
                int mn = inf;
                for (int i = lb; i <= rb; i++)
                    mn = min(mn, mnl[i]);
                lb = mn;
                if (r < lb) break;
                rb = r;
                res++;
            }
            ans[ei][j] = res + 1;
        }
    }
 
    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
 
        if (s == e) {
            cout << "0\n";
            continue;
        }
 
        int si = 0, ei = 0;
        for (int j = 0; j < n; j++) {
            if (ev[j].i == s) si = j;
            if (ev[j].i == e) ei = j;
        }
 
        if (ans[ei][si] < inf) cout << ans[ei][si] << '\n';
        else cout << "impossible\n";
    }
 
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<event> ev(n), og;
    map<int,int> comp;
    int _i = 0;
    for (auto& [s, e, i] : ev) {
        cin >> s >> e;
        comp[s] = comp[e] = 0;
        i = _i++;
    }
    int k = 0;
    for (auto& mp : comp)
        mp.second = k++;
    for (auto& [s, e, i] : ev)
        s = comp[s], e = comp[e];
 
    og = ev;
    sort(ev.begin(), ev.end(), [&](auto& a, auto& b) {
        return a.r == b.r ? a.l < b.l : a.r < b.r ;
    });

    bool overlap = 0;
    for (int i = 0; i+1 < n;i ++) {
        if (ev[i].l > ev[i+1].l) overlap = 1;
    }
    //for (auto[a,b,c] : ev) cout << a << ' ' << b << ' ' << c <<'\n';
    if (!overlap) subtask_5(n, m, k, ev, og);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 475 ms 19316 KB Output is correct
2 Correct 449 ms 19316 KB Output is correct
3 Correct 439 ms 19304 KB Output is correct
4 Correct 515 ms 27616 KB Output is correct
5 Correct 514 ms 19628 KB Output is correct
6 Correct 595 ms 27224 KB Output is correct
7 Correct 595 ms 27224 KB Output is correct
8 Correct 572 ms 27336 KB Output is correct
9 Correct 266 ms 26468 KB Output is correct
10 Correct 528 ms 26940 KB Output is correct
11 Correct 480 ms 26928 KB Output is correct
12 Correct 470 ms 26864 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -