#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 subtask_1(int n, int m, int k, vector<event>& ev, vector<event>& og) {
vector<vector<int>> byr(k);
for (int i = 0; i < n;i++) {
byr[ev[i].r].push_back(i);
}
vector<int> next(n, -1), dist(n, inf), cc(n, -1);
for (int i = 0; i < n;i++) {
for (int j = ev[i].l; j <= ev[i].r; j++) {
for (int t : byr[j]) {
next[t] = i;
}
}
}
int C = 0;
cc[n-1] = dist[n-1] = C++;
for (int i = n-2; i >= 0; i--) {
if (next[i] !=-1) {
dist[i] = min(dist[i], 1 + dist[next[i]]);
cc[i] = cc[next[i]];
}
else cc[i] = C++, dist[i] = 0;
}
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--;
s = iof[s], e = iof[e];
if (cc[s] != cc[e] || dist[s] < dist[e]) cout << "impossible\n";
else cout << dist[s] - dist[e] << '\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';
return subtask_1(n, m, k, ev, og);
if (!overlap) return subtask_5(n, m, k, ev, og);
else if (n <= 5000) return subtask_3(n, m, k, ev, og);
else if (m <= 100) return subtask_4(n, m, k, ev, og);
else return subtask_1(n, m, k, ev, og);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
379 ms |
14952 KB |
Output is correct |
| 2 |
Correct |
346 ms |
15020 KB |
Output is correct |
| 3 |
Correct |
366 ms |
14900 KB |
Output is correct |
| 4 |
Incorrect |
389 ms |
21620 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
