#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 2e5 + 10, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll S[n_], E[n_], par[n_][20], rev[n_], res[n_];
vector<PP> Q[n_];
vector<P> U[n_];
bool cmp(ll x, ll y) {
if (E[x] ^ E[y]) return E[x] < E[y];
return S[x] < S[y];
}
class seg {
public:
vector<ll> tree;
ll base;
seg(int n) {
for (base = 1; base <= n; base *= 2);
// 0~n쓰겠다
tree.resize(n * 4 + 4);
for (int i = 0; i < tree.size(); i++) tree[i] = inf;
}
ll f(ll l, ll r) {
l += base, r += base;
ll ret = inf;
while (l <= r) {
if (l % 2) ret = min(ret, tree[l++]);
if (!(r % 2)) ret = min(ret, tree[r--]);
l /= 2, r /= 2;
}
return ret;
}
void update(ll i, ll v) {
i += base;
tree[i] = min(tree[i], v);
i /= 2;
while (i) {
tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
i /= 2;
}
}
};
//! 주의 0이 lover_bound입니다.
class lazy_seg {
public:
vector<ll> tree, lazy, A;
lazy_seg() {}
lazy_seg(int n) {
// 0~n까지 쓰겠다.
tree.resize(n * 4);
lazy.resize(n * 4);
A.resize(n * 4);
}
ll init(ll N, ll s, ll e) {
if (s == e) return tree[N] = A[s];
ll mid = (s + e) / 2;
return tree[N] = max(init(N * 2, s, mid), init(N * 2 + 1, mid + 1, e));
}
void update_lazy(ll N, ll s, ll e) {
if (!lazy[N]) return;
tree[N] = max(tree[N], lazy[N]);
if (s != e) {
lazy[N * 2] = max(lazy[N * 2], lazy[N]);
lazy[N * 2 + 1] = max(lazy[N * 2 + 1], lazy[N]);
}
lazy[N] = 0;
}
void update(ll N, ll s, ll e, ll l, ll r, ll val) {
update_lazy(N, s, e);
if (l > e || r < s) return;
if (l <= s && e <= r) {
lazy[N] = val;
update_lazy(N, s, e);
return;
}
ll mid = (s + e) / 2;
update(N * 2, s, mid, l, r, val);
update(N * 2 + 1, mid + 1, e, l, r, val);
tree[N] = max(tree[N * 2], tree[N * 2 + 1]);
}
ll f(ll N, ll s, ll e, ll l, ll r) {
update_lazy(N, s, e);
if (l > e || r < s) return 0;
if (l <= s && e <= r) return tree[N];
ll mid = (s + e) / 2;
return max(f(N * 2, s, mid, l, r), f(N * 2 + 1, mid + 1, e, l, r));
}
};
lazy_seg ST[20];
ll go(ll now, ll x) {
for (int i = 19; i >= 0; i--) {
if (x >= (1ll << i)) {
now = ST[i].f(1, 0, n - 1, now, now);
x -= (1ll << i);
}
}
return now;
}
void solve() {
ll q;
cin >> n >> q;
vector<ll> T, idx;
for (int i = 1; i <= n; i++) {
cin >> S[i] >> E[i];
T.push_back(S[i]), T.push_back(E[i]);
idx.push_back(i);
}
sort(all(idx), cmp), sort(all(T)), T.erase(unique(all(T)), T.end());
for (int i = 0; i < n; i++) {
rev[idx[i]] = i;
ll e = lower_bound(all(T), E[idx[i]]) - T.begin();
U[e].push_back({S[idx[i]], i});
}
for (int i = 0; i < q; i++) {
cin >> x >> y;
if (x != y) {
x = rev[x], y = rev[y];
ll a = lower_bound(all(T), E[idx[y]]) - T.begin();
Q[a].push_back({i, {x, y}});
}
}
for (int i = 0; i < 18; i++) {
lazy_seg T(n);
for (int j = 0; j < n; j++) T.A[j] = j;
T.init(1, 0, n - 1);
ST[i] = T;
}
seg ST2(n + 1);
for (int i = 0; i < n; i++) ST2.update(i, S[idx[i]]);
for (int i = 0; i < n_; i++) {
if (U[i].size()) {
sort(all(U[i]));
ll s = U[i][0].first, e = T[i], L = inf, R = -inf, l, r;
l = 0, r = n - 1;
while (l <= r) {
ll mid = (l + r) / 2;
if (E[idx[mid]] <= e) {
R = max(R, mid);
l = mid + 1;
} else
r = mid - 1;
}
for (int j = 0; j < 18; j++) {
l = 0, r = n - 1;
ll bef = R;
while (l <= r) {
ll mid = (l + r) / 2;
if (E[idx[mid]] >= s) {
L = min(L, mid);
r = mid - 1;
} else
l = mid + 1;
}
if (L <= R) {
ST[j].update(1, 0, n - 1, L, R, U[i][0].second);
s = ST2.f(L, R);
} else
break;
}
}
for (auto [x, cur] : Q[i]) {
ll now = cur.first, cost = 0;
for (int j = 17; j >= 0; j--) {
ll val = (1ll << j);
if (E[idx[go(now, val - 1)]] >= S[idx[cur.second]]) continue;
cost += val;
now = go(now, val);
}
now = idx[now];
if (E[now] < S[idx[cur.second]] || E[now] > E[idx[cur.second]])
res[x] = -1;
else
res[x] = cost + 1;
}
}
for (int i = 0; i < q; i++) {
if (res[i] == -1)
cout << "impossible";
else
cout << res[i];
cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// cin >> tc;
while (tc--) solve();
};
Compilation message
events.cpp: In constructor 'seg::seg(int)':
events.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i = 0; i < tree.size(); i++) tree[i] = inf;
| ~~^~~~~~~~~~~~~
events.cpp: In function 'void solve()':
events.cpp:149:20: warning: unused variable 'bef' [-Wunused-variable]
149 | ll bef = R;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 2 |
Execution timed out |
1596 ms |
202000 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
11612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
11612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
11612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1525 ms |
200596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 2 |
Execution timed out |
1596 ms |
202000 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
