#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
struct item {
int L, R;
item() : L(INT_MAX), R(0) {}
item (int L, int R) : L(L), R(R) {}
bool operator < (const item &o) const {
if (R == o.R) return L < o.L;
return R < o.R;
}
} event[mn];
struct IT {
vector<int> tr;
IT (int sz) : tr(4 * sz) {}
int opr (int a, int b) {
return (event[a].L < event[b].L ? a : b);
}
void update (int pos, int val, int k, int l, int r) {
for (; l < r;) {
int mid = (l + r) >> 1;
if (pos <= mid) k <<= 1, r = mid;
else k <<= 1, k |= 1, l = mid + 1;
}
tr[k] = opr(tr[k], val);
for (k /= 2; k; k /= 2)
tr[k] = opr(tr[k << 1], tr[k << 1 | 1]);
}
int query (int a, int b, int k, int l, int r) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return tr[k];
int mid = (l + r) >> 1;
return opr(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
}
};
vector<int> cmp;
int nxt[18][mn];
int getID (int targ) {
return lower_bound(all(cmp), targ) - cmp.begin();
}
int main()
{
freopen("EVENTS.inp", "r", stdin);
freopen("EVENTS.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> event[i].L >> event[i].R;
cmp.push_back(event[i].L), cmp.push_back(event[i].R);
}
sort(all(cmp)), filter(cmp);
vector<int> ord(n);
for (int i = 1; i <= n; i++) ord[i - 1] = i;
sort(all(ord), [&] (int a, int b) { return event[a].R < event[b].R; });
IT tree(cmp.size());
for (int i : ord) {
event[i].L = getID(event[i].L), event[i].R = getID(event[i].R);
tree.update(event[i].R, i, 1, 0, cmp.size() - 1);
nxt[0][i] = tree.query(event[i].L, event[i].R, 1, 0, cmp.size() - 1);
// cout << "next " << i << " -> " << nxt[0][i] << "\n";
}
for (int s = 1; s < 18; s++)
for (int i = 1; i <= n; i++)
nxt[s][i] = nxt[s - 1][nxt[s - 1][i]];
for (int i = 0; i < q; i++) {
int s, e; cin >> s >> e;
if (s == e) {
cout << 0 << "\n";
continue;
}
if (event[s].R > event[e].R) {
cout << "impossible\n";
continue;
}
if (event[e].L <= event[s].R) {
cout << 1 << "\n";
continue;
}
int ans = 0;
for (int lift = 17; lift >= 0; lift--) {
if (event[nxt[lift][e]].L > event[s].R) e = nxt[lift][e], ans |= (1 << lift);
}
e = nxt[0][e], ans++;
if (event[e].L > event[s].R) cout << "impossible\n";
else cout << ans + 1 << "\n";
}
return 0;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | freopen("EVENTS.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | freopen("EVENTS.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
