#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, INF = 1e9 + 10;
struct SegTreeMin
{
int l, r, mid;
SegTreeMin *lc, *rc;
int val = INF;
SegTreeMin(int l_, int r_) : l(l_), r(r_)
{
mid = (l + r) / 2;
if (l == r - 1)
{
return;
}
lc = new SegTreeMin(l, mid);
rc = new SegTreeMin(mid, r);
}
~SegTreeMin()
{
if (l == r - 1)
{
return;
}
delete lc;
delete rc;
}
void update(int i, int u)
{
if (l == r - 1)
{
val = u;
return;
}
if (i < mid)
{
lc->update(i, u);
}
else
{
rc->update(i, u);
}
val = min(lc->val, rc->val);
}
int query(int ll, int rr)
{
if (ll <= l && rr >= r)
{
return val;
}
int ret = INF;
if (ll < mid)
{
ret = min(ret, lc->query(ll, rr));
}
if (mid < rr)
{
ret = min(ret, rc->query(ll, rr));
}
return ret;
}
};
struct SegTree
{
int l, r, mid;
SegTree *lc, *rc;
vector<int> val;
SegTree(int l_, int r_) : l(l_), r(r_)
{
mid = (l + r) / 2;
if (l == r - 1)
{
return;
}
lc = new SegTree(l, mid);
rc = new SegTree(mid, r);
}
void add(int ll, int rr, int id)
{
if (ll <= l && rr >= r)
{
val.push_back(id);
return;
}
if (ll < mid)
{
lc->add(ll, rr, id);
}
if (mid < rr)
{
rc->add(ll, rr, id);
}
}
void query(int i, vector<int> &ans)
{
ans.insert(ans.end(), val.begin(), val.end());
val.clear();
if (l == r - 1)
{
return;
}
if (i < mid)
{
lc->query(i, ans);
}
else
{
rc->query(i, ans);
}
}
};
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
l--;
a[i] = make_pair(l, r);
}
vector<int> dpl(n, INF), dpr(n, INF);
SegTreeMin stl(0, n);
stl.update(0, 0);
dpl[0] = 0;
for (int i = 1; i < n; i++)
{
dpl[i] = min(dpl[i], a[i].first > 0 ? 1 + stl.query(a[i].first, i) : 0);
stl.update(i, dpl[i]);
}
SegTreeMin str(0, n);
str.update(n - 1, 0);
dpr[n - 1] = 0;
for (int i = n - 2; i >= 0; i--)
{
dpr[i] = a[i].second < n ? 1 + str.query(i, a[i].second) : 0;
str.update(i, dpr[i]);
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
for (int i = 0; i < n; i++)
{
pq.emplace(min(INF, min(dpl[i], 1 + stl.query(a[i].first, a[i].second)) + min(dpr[i], 1 + str.query(a[i].first, a[i].second))), i);
}
vector<int> ans(n, INF);
SegTree st(0, n);
for (int i = 0; i < n; i++)
{
st.add(a[i].first, a[i].second, i);
}
while (pq.size())
{
auto [d, i] = pq.top();
pq.pop();
if (ans[i] != INF)
{
continue;
}
ans[i] = d;
vector<int> res;
st.query(i, res);
for (int j : res)
{
if (ans[j] == INF)
{
pq.emplace(d + 1, j);
}
}
}
int q;
cin >> q;
while (q--)
{
int i;
cin >> i;
i--;
cout << (ans[i] == INF ? -1 : ans[i] + 1) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
