This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e5 + 5, INF = 1e9;
int n, q;
array<int, MAX_N> l, r;
vector<pii> ord; // {r, i}
int n_ccs;
unordered_map<int, int> cc;
void precomp() {
for (int i = 1; i <= n; i++) ord.push_back({r[i], i});
sort(ord.rbegin(), ord.rend());
set<int> coords;
for (int i = 1; i <= n; i++) coords.insert(l[i]), coords.insert(r[i]);
while (coords.size()) {
n_ccs++, cc[*coords.begin()] = n_ccs;
coords.erase(coords.begin());
}
}
array<int, 8 * MAX_N> st;
void update(int l, int r, int x, int u = 1, int lo = 1, int hi = n_ccs) {
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) { st[u] = min(st[u], x); return; }
int mid = (lo + hi) / 2;
update(l, r, x, 2 * u, lo, mid), update(l, r, x, 2 * u + 1, mid + 1, hi);
}
int query(int i, int u = 1, int lo = 1, int hi = n_ccs) {
if (i < lo || hi < i) return INF;
if (lo == hi) return st[u];
int mid = (lo + hi) / 2;
return min({st[u], query(i, 2 * u, lo, mid), query(i, 2 * u + 1, mid + 1, hi)});
}
array<int, MAX_N> dp;
void comp(int f) {
fill(st.begin(), st.end(), INF);
for (pii x : ord) {
int i = x.second;
if (i == f) dp[i] = 0;
else if (l[f] <= r[i] && r[i] <= r[f]) dp[i] = 1;
else dp[i] = query(cc[r[i]]) + 1;
update(cc[l[i]], cc[r[i]], dp[i]);
}
}
int main() {
// freopen("event.in", "r", stdin);
cin.sync_with_stdio(false), cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
precomp();
for (int i = 1; i <= q; i++) {
int s, f; cin >> s >> f;
comp(f);
if (dp[s] >= INF) cout << "impossible" << '\n';
else cout << dp[s] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |