#include <bits/stdc++.h>
#define fr(i, a, b) for (int i = a; i <= b; ++i)
#define rf(i, a, b) for (int i = a; i >= b; --i)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
using namespace std;
template <typename T>
using ve = vector < T >;
template <typename T>
bool umx(T& a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T>
bool umn(T& a, T b) {return a > b ? a = b, 1 : 0;}
using ll = long long;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
const int N = 2e5 + 100;
const int oo = 1e9 + 10;
const ll OO = 1e18 + 100;
pii event[N];
pii rl[N];
int mas[N];
int n, q;
map <int, bool> have;
struct segTree {
ve <int> mas;
ve <int> T;
ve <int> T1;
segTree(ve<int>& data) {
mas = data;
T.resize(4 * sz(data));
T1.resize(4 * sz(data), oo);
build(1, 0, sz(mas) - 1);
}
void push(int v) {
if(T1[v] == oo) return;
for(auto to : {v << 1, v << 1 | 1}) {
umn(T1[to], T1[v]);
umn(T[to], T1[v]);
}
T1[v] = oo;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
T[v] = mas[tl];
return;
}
int tm = (tl + tr) >> 1;
build(v << 1, tl, tm);
build(v << 1 | 1, tm + 1, tr);
T[v] = min(T[v << 1 | 1], T[v << 1]);
}
int get(int v, int tl, int tr, int ps) {
if (tl == tr) {
return T[v];
}
int tm = (tl + tr) >> 1;
push(v);
if (tm >= ps) return get(v << 1, tl, tm, ps);
else return get(v << 1 | 1, tm + 1, tr, ps);
}
void upd(int v, int tl, int tr, int l, int r, int vl) {
if (l > r) return;
if (tl == l && tr == r) {
T[v] = min(T[v], vl);
T1[v] = min(T1[v], vl);
return;
}
push(v);
int tm = (tl + tr) >> 1;
upd(v << 1, tl, tm, l, min(r, tm), vl);
upd(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, vl);
T[v] = min(T[v << 1], T[v << 1 | 1]);
}
int get(int ps) {
return get(1, 0, sz(mas) - 1, ps);
}
void upd(int l, int r, int vl) {
upd(1, 0, sz(mas) - 1, l, r, vl);
}
};
void slv(int st, int nd) {
if (st == nd) {
cout << "0\n";
return;
}
if (rl[st].fi > rl[nd].se) {
cout << "Impossible\n";
return;
}
ve <int> v(n, oo);
int start = 0, fn = 0;
fr(i, 0, n - 1) {
if (event[i] == rl[st]) {
v[i] = 0;
start = i;
}
if (event[i] == rl[nd]) {
fn = i;
}
}
segTree T(v);
// return;
fr(i, start, n - 1) {
int vl = T.get(i);
int ptr = upper_bound(event, event + n, make_pair(event[i].se, oo)) - event;
if (ptr == n || event[ptr].fi > event[i].se) ptr--;
T.upd(i, ptr, vl + 1);
}
int x = T.get(fn);
if (x == oo)cout << "Impossible\n";
else cout << x << '\n';
}
int main() {
#ifdef local
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // local
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
fr(i, 0, n - 1) {
cin >> event[i].fi >> event[i].se;
rl[i] = event[i];
}
sort(event, event + n);
// fr(i, 0, n - 1) {
// cout << event[i].fi << " " << event[i].se << "\n";
// }
fr(i, 0, n - 1) {
have[event[i].se] = 1;
mas[i] = event[i].se;
if (i) umx(mas[i], mas[i - 1]);
}
while(q--) {
int s, e;
cin >> s >> e; s--; e--;
slv(s, e);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1554 ms |
11424 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
