oj.uz

Submission #673966

# Submission time Handle Problem Language Result Execution time Memory
673966 2022-12-22T13:23:38 Z stanislavpolyn Event Hopping (BOI22_events) C++17
45 / 100
 1500 ms 14212 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 mp make_pair
#define mt make_tuple

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

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 1e5 + 5;

int n, q;
pii a[N];

ve<int> order;

int to[N];
int d[N];
ve<pii> Q[N];
int ans[N];
//bool subtask1 = 1;

pii get(int v) {
    if (to[v] == v) {
        return {v, 0};
    } else {
        pii p = get(to[v]);
        p.se += d[v];
        to[v] = p.fi;
        d[v] = p.se;
        return {p.fi, p.se};
    }
}

bool TL() {
    return (double)clock() / CLOCKS_PER_SEC > 1.4;
}

ve<int> st;

bool have[N];
bool subtask = 1;
bool subtask1;

int go[N][20];

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> q;

//    subtask1 &= n > 5000 || q > 100;

    ve<int> u;
    fr (i, 1, n) {
        cin >> a[i].fi >> a[i].se;
        order.pb(i);
        u.pb(a[i].se);
    }

    sort(all(u));

    {
        sort(all(order), [](int i, int j) {
            return a[i].fi < a[j].fi || (a[i].fi == a[j].fi && a[i].se > a[j].se);
        });

        fe (i, order) {
            if (sz(st) && a[st.back()].se >= a[i].se) {
                to[i] = st.back();
                continue;
            }
            st.pb(i);
            have[i] = 1;
        }


        fr (i, 1, sz(st) - 1) {
            assert(a[st[i]].fi > a[st[i - 1]].fi);
            assert(a[st[i]].se > a[st[i - 1]].se);
        }

        {
            int mx = -1e9;
            int mxI = -1;
            int ptr = 0;

            fe (i, st) {
                while (ptr < sz(st) && a[st[ptr]].fi <= a[i].se) {
                    if (umx(mx, a[st[ptr]].se)) {
                        mxI = st[ptr];
                    }
                    ptr++;
                }

                if (mx >= a[i].se) {
                    to[i] = mxI;
                } else {
                    assert(0);
                    to[i] = -1;
                }
            }
        }

        subtask &= sz(st) == n;
    }

    if (subtask) {
        fr (i, 1, n) {
            go[i][0] = to[i];
        }
        fr (p, 1, 19) {
            fr (i, 1, n) {
                go[i][p] = go[go[i][p - 1]][p - 1];
            }
        }

        fr (i, 1, q) {
            int s, e;
            cin >> s >> e;

            if (s == e) {
                cout << "0\n";
                continue;
            }

            if (a[s].se > a[e].se) {
                cout << "impossible\n";
                continue;
            }

            int v = s;
            int ans = 0;

            rf (p, 19, 0) {
                if (!go[v][p]) continue;

                int nxt = go[v][p];
                if (a[nxt].se < a[e].se) {
                    v = go[v][p];
                    ans += pw(p);
                }
            }

            while (1) {
                if (a[to[v]].se == a[v].se || a[to[v]].se > a[e].se || a[v].se >= a[e].fi) {
                    break;
                }
                v = to[v];
                ans++;
            }

            if (a[v].se >= a[e].fi) {
                ans++;
                cout << ans << "\n";
            } else {
                cout << "impossible\n";
            }

        }


        return 0;
    }

//    fr (i, 1, n) {
//        int p1 = lower_bound(all(u), a[i].fi) - u.begin();
//        int p2 = upper_bound(all(u), a[i].se) - u.begin() - 1;
//        if (max(0, p2 - p1 + 1) > 2) {
//            assert(0);
//        }
//    }

//    fr (i, 1, n) {
//        int cnt = 0;
//        fr (j, 1, n) {
//            if (i == j) continue;
//
//            if (a[j].fi <= a[i].se && a[i].se <= a[j].se) {
//                cnt++;
//            }
//        }
//        assert(cnt <= 1);
//    }

    fr (i, 1, q) {
        int s, e;
        cin >> s >> e;

        if (s == e) {
            ans[i] = 0;
            continue;
        }

        if (a[s].se >= a[e].fi && a[s].se <= a[e].se) {
            ans[i] = 1;
            continue;
        }

        if (a[s].se > a[e].se) {
            ans[i] = -1;
            continue;
        }
        Q[e].pb({s, i});
    }


    sort(all(order), [](int i, int j) {
        return a[i].se < a[j].se || (a[i].se == a[j].se && a[i].fi < a[j].fi);
    });

    fr (i, 1, n) {
        to[i] = i;
        d[i] = 0;
    }

//    subtask1 = 1;

//    if (q > 100 || n > 5000) {
        subtask1 = 1;
//    }

    ve<pii> add, del;
    fr (idx, 0, sz(order) - 1) {
        int i = order[idx];

        int l = 0;
        int r = idx - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            int j = order[mid];

            if (a[j].se < a[i].fi) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        if (a[order[l]].se < a[i].fi) {
            l++;
        }

        if (l <= idx - 1) {

//            rf (ptr, idx - 1, l) {
//                int j = order[ptr];
//                to[j] = i;
//                d[j] = 1;
//            }

            add.pb({l, idx});
            del.pb({idx, idx});
        }

//        rf (ptr, idx - 1, 0) {
//            int j = order[ptr];
//            if (a[j].se < a[i].fi) {
//                break;
//            }
//
//            subtask1 &= ptr == idx - 1;
//            to[j] = i;
//            d[j] = 1;
//        }

        if (sz(Q[i])) {
            sort(all(add));
            sort(all(del));
//
            int ptr1 = 0;
            int ptr2 = 0;
            set<int> s;
            fr (cur, 0, idx) {
                while (ptr1 < sz(add) && add[ptr1].fi <= cur) {
                    s.insert(add[ptr1].se);
                    ptr1++;
                }
                while (ptr2 < sz(del) && del[ptr2].fi <= cur) {
                    s.erase(del[ptr2].se);
                    ptr2++;
                }

                int i = order[cur];

                if (sz(s)) {
                    d[i] = 1;
//                    assert(to[i] == order[*s.rbegin()]);
                    to[i] = order[*s.rbegin()];
                }
            }

            add.clear();
            del.clear();
        }

        fe (cur, Q[i]) {
            if (subtask1) {
                auto p = get(cur.fi);

                if (p.fi == i) {
                    ans[cur.se] = p.se;
                } else {
                    ans[cur.se] = -1;
                }
            } else {
                int v = cur.fi;
                int sum = 0;
                while (to[v] != v) {
                    sum += d[v];
                    v = to[v];
                }

                if (v == i) {
                    ans[cur.se] = sum;
                } else {
                    ans[cur.se] = -1;
                }
            }
        }
    }

    fr (i, 1, q) {
        if (ans[i] == -1) {
            cout << "impossible\n";
        } else {
            cout << ans[i] << "\n";
        }
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 73 ms 13568 KB Output is correct
3 Correct 80 ms 13576 KB Output is correct
4 Correct 105 ms 13676 KB Output is correct
5 Correct 231 ms 12812 KB Output is correct
6 Correct 208 ms 12232 KB Output is correct
7 Correct 207 ms 12072 KB Output is correct
8 Correct 170 ms 7560 KB Output is correct
9 Correct 85 ms 14144 KB Output is correct
10 Correct 101 ms 13984 KB Output is correct
11 Execution timed out 1584 ms 6824 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Incorrect 41 ms 5108 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Correct 3 ms 2644 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 51 ms 13036 KB Output is correct
20 Correct 70 ms 5512 KB Output is correct
21 Correct 92 ms 5236 KB Output is correct
22 Correct 65 ms 6004 KB Output is correct
23 Correct 52 ms 13048 KB Output is correct
24 Correct 52 ms 13056 KB Output is correct
25 Correct 29 ms 7364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 13688 KB Output is correct
2 Correct 88 ms 13568 KB Output is correct
3 Correct 140 ms 13572 KB Output is correct
4 Correct 76 ms 14212 KB Output is correct
5 Correct 102 ms 14028 KB Output is correct
6 Correct 100 ms 13724 KB Output is correct
7 Correct 112 ms 13732 KB Output is correct
8 Correct 77 ms 13952 KB Output is correct
9 Correct 47 ms 13004 KB Output is correct
10 Correct 79 ms 13432 KB Output is correct
11 Correct 72 ms 13248 KB Output is correct
12 Correct 83 ms 13428 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 73 ms 13568 KB Output is correct
3 Correct 80 ms 13576 KB Output is correct
4 Correct 105 ms 13676 KB Output is correct
5 Correct 231 ms 12812 KB Output is correct
6 Correct 208 ms 12232 KB Output is correct
7 Correct 207 ms 12072 KB Output is correct
8 Correct 170 ms 7560 KB Output is correct
9 Correct 85 ms 14144 KB Output is correct
10 Correct 101 ms 13984 KB Output is correct
11 Execution timed out 1584 ms 6824 KB Time limit exceeded
12 Halted 0 ms 0 KB -