oj.uz

답안 #673989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673989 2022-12-22T13:47:59 Z gesgha Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 11424 KB 
#include <bits/stdc++.h>
#define fr(i, a, b) for (int i = a; i <= b; ++i)
#define rf(i, a, b) for (int i = a; i >= b; --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))

using namespace std;

template <typename T>
using ve = vector < T >;

template <typename T>
bool umx(T& a, T b) {return a < b ? a = b, 1 : 0;}

template <typename T>
bool umn(T& a, T b) {return a > b ? a = b, 1 : 0;}

using ll = long long;
using pll = pair <ll, ll>;
using pii = pair <int, int>;

const int N = 2e5 + 100;
const int oo = 1e9 + 10;
const ll OO = 1e18 + 100;


pii event[N];
pii rl[N];



int mas[N];
int n, q;
map <int, bool> have;



struct segTree {
    ve <int> mas;
    ve <int> T;
    ve <int> T1;
    segTree(ve<int>& data) {
        mas = data;
        T.resize(4 * sz(data));
        T1.resize(4 * sz(data), oo);
        build(1, 0, sz(mas) - 1);
    }
    void push(int v) {
        if(T1[v] == oo) return;
        for(auto to : {v << 1, v << 1 | 1}) {
            umn(T1[to], T1[v]);
            umn(T[to], T1[v]);
        }
        T1[v] = oo;
    }

    void build(int v, int tl, int tr) {
        if (tl == tr) {
            T[v] = mas[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);
        T[v] = min(T[v << 1 | 1], T[v << 1]);
    }

    int get(int v, int tl, int tr, int ps) {
        if (tl == tr) {
            return T[v];
        }
        int tm = (tl + tr) >> 1;
        push(v);
        if (tm >= ps) return get(v << 1, tl, tm, ps);
        else return get(v << 1 | 1, tm + 1, tr, ps);
    }

    void upd(int v, int tl, int tr, int l, int r, int vl) {
        if (l > r) return;
        if (tl == l && tr == r) {
            T[v] = min(T[v], vl);
            T1[v] = min(T1[v], vl);
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        upd(v << 1, tl, tm, l, min(r, tm), vl);
        upd(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, vl);
        T[v] = min(T[v << 1], T[v << 1 | 1]);
    }
    int get(int ps) {
        return get(1, 0, sz(mas) - 1, ps);
    }
    void upd(int l, int r, int vl) {
        upd(1, 0, sz(mas) - 1, l, r, vl);
    }
};


void slv(int st, int nd) {
    if (st == nd) {
        cout << "0\n";
        return;
    }
    if (rl[st].fi > rl[nd].se) {
        cout << "Impossible\n";
        return;
    }
    ve <int> v(n, oo);
    int start = 0, fn = 0;
    fr(i, 0, n - 1) {
        if (event[i] == rl[st]) {
            v[i] = 0;
            start = i;
        }
        if (event[i] == rl[nd]) {
            fn = i;
        }
    }

    segTree T(v);
//    return;
    fr(i, start, n - 1) {
        int vl = T.get(i);
        int ptr = upper_bound(event, event + n, make_pair(event[i].se, oo)) - event;
        if (ptr == n || event[ptr].fi > event[i].se) ptr--;

        T.upd(i, ptr, vl + 1);
    }
    int x = T.get(fn);
    if (x == oo)cout << "Impossible\n";
    else cout << x << '\n';
}


int main() {
#ifdef local
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // local
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    fr(i, 0, n - 1) {
        cin >> event[i].fi >> event[i].se;
        rl[i] = event[i];
    }
    sort(event, event + n);
//    fr(i, 0, n - 1) {
//        cout << event[i].fi << " " << event[i].se << "\n";
//    }
    fr(i, 0, n - 1) {
        have[event[i].se] = 1;
        mas[i] = event[i].se;
        if (i) umx(mas[i], mas[i - 1]);
    }
    while(q--) {
        int s, e;
        cin >> s >> e; s--; e--;
        slv(s, e);
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1554 ms 11424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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