#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 1e5 + 5;
ll n, q, s[N], e[N];
vector <int> cmp, out[2 * N], in[2 * N];
vector <int> d[N];
const ll Nmax = 5005;
int dist[Nmax][Nmax];
void bfs(int st, int *f) {
rep(i, 1, n) f[i] = 1e9;
f[st] = 0;
queue <int> q;
q.push(st);
while (q.size()) {
int u = q.front(); q.pop();
for (int v: d[u]) if (f[v] > f[u] + 1) {
f[v] = f[u] + 1;
q.push(v);
}
}
}
namespace sub4 {
pii a[N];
ll pos[N], f[N];
void solve() {
rep(i, 1, n) a[i] = {e[i], i};
sort(a + 1, a + 1 + n);
rep(i, 1, n) pos[a[i].nd] = i;
while (q --) {
int u, v;
cin >> u >> v;
int i = pos[u];
int j = pos[v];
int l = j;
if (i > j && a[j].st < a[i].st) {
cout << "impossible\n";
continue;
}
if (i > j) {
cout << 1 << '\n';
continue;
}
while (l + 1 <= n && a[l + 1].st == a[j].st) l ++;
f[l + 1] = 1e9;
//cout << i << ' ' << j << '\n';
rrep(k, l, i) {
int id = a[k].nd;
f[k] = min(f[k + 1], s[id]);
}
int ans = 0;
while (i < j) {
ans ++;
int cur = a[i].st, pre = i;
while (i < l && cur >= f[i + 1]) {
i ++;
}
if (i > j) {
int id = a[j].nd;
if (cur >= s[v] && cur <= e[v])
break;
ans ++;
break;
}
if (i == pre) break;
}
//cout << i << ' ' << j << '\n';
if (i >= j)
cout << ans << '\n';
else
cout << "impossible\n";
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("events.inp", "r", stdin);
freopen("events.out", "w", stdout);
cin >> n >> q;
rep(i, 1, n)
cin >> s[i] >> e[i];
if (q <= 100) {
sub4 :: solve();
return 0;
}
rep(i, 1, n) rep(j, 1, n) if (i != j)
if (s[j] <= e[i] && e[i] <= e[j])
d[i].push_back(j);
rep(i, 1, n) bfs(i, dist[i]);
while (q --) {
int u, v;
cin >> u >> v;
if (dist[u][v] >= (int)1e9)
cout << "impossible\n";
else
cout << dist[u][v] << '\n';
}
return 0;
}
Compilation message
events.cpp: In function 'void sub4::solve()':
events.cpp:74:25: warning: unused variable 'id' [-Wunused-variable]
74 | int id = a[j].nd;
| ^~
events.cpp: In function 'int main()':
events.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | freopen("events.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen("events.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
