#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()
const int mxn = 2e5 + 100;
vector<pair<ll, ll>> v;
vector<int> dg[mxn], g[mxn];
struct Node {
ll lp = -1, rp = -1, r = -1, ind = -1, lz = -1, lzind = -1;
} null;
struct Query {
ll l1, r1, l2, r2, ans, ind;
};
struct SGT {
ll cnt = 2;
vector<Node> sgt;
SGT(ll sz) {
sgt.resize(8 * sz);
}
void set(ll &x, ll &y, ll &s1, ll &s2) {
if (x == -1) x = cnt++;
if (y == -1) y = cnt++;
s1 = x, s2 = y;
}
void push(ll k, ll l, ll r) {
if (sgt[k].lz != -1) {
if (sgt[k].lz > sgt[k].r) sgt[k].ind = sgt[k].lzind;
sgt[k].r = max(sgt[k].r, sgt[k].lz);
if (l != r) {
ll lp, rp;
set(sgt[k].lp, sgt[k].rp, lp, rp);
sgt[lp].lz = sgt[k].lz;
sgt[rp].lz = sgt[k].lz;
sgt[lp].lzind = sgt[k].lzind;
sgt[rp].lzind = sgt[k].lzind;
}
sgt[k].lz = sgt[k].lzind = -1;
}
}
void merge(Node &k, Node k1, Node k2) {
k.r = max(k1.r, k2.r);
if (k1.r > k2.r) k.ind = k1.ind;
else k.ind = k2.ind;
}
void update(ll k, ll l, ll r, ll i, ll j, ll ind) {
push(k, l, r);
if (l > j || r < i) return;
if (i <= l && r <= j) {
sgt[k].lz = j;
sgt[k].lzind = ind;
push(k, l, r);
return;
}
ll mid = (l + r) / 2;
ll lp, rp;
set(sgt[k].lp, sgt[k].rp, lp, rp);
update(lp, l, mid, i, j, ind);
update(rp, mid + 1, r, i, j, ind);
merge(sgt[k], sgt[lp], sgt[rp]);
}
Node get(ll k, ll l, ll r, ll i) {
push(k, l, r);
if (l > i || r < i) return null;
if (l == r) return sgt[k];
ll mid = (l + r) / 2;
ll lp, rp;
set(sgt[k].lp, sgt[k].rp, lp, rp);
Node ansL = get(lp, l, mid, i), ansR = get(rp, mid + 1, r, i);
Node ans;
merge(ans, ansL, ansR);
return ans;
}
} sgt(mxn);
struct sgtINT {
vector<ll> sgt;
sgtINT(int sz) {
sgt.resize(8 * sz, -1);
}
void update(int k, int l, int r, int i, ll val) {
if (l > i || r < i) return;
if (l == r) {
sgt[k] = max(sgt[k], val);
return;
}
int mid = (l + r) / 2;
update(k * 2, l, mid, i, val);
update(k * 2 + 1, mid + 1, r, i, val);
sgt[k] = max(sgt[k * 2], sgt[k * 2 + 1]);
}
ll get(int k, int l, int r, int i, int j) {
if (l > j || r < i) return -1;
if (i <= l && r <= j) return sgt[k];
int mid = (l + r) / 2;
return max(get(k * 2, l, mid, i, j), get(k * 2 + 1, mid + 1, r, i, j));
}
} con(mxn);
vector<int> ord;
bool visited[mxn];
void dfs(int cur, int par = -1) {
visited[cur] = 1;
for (auto x : dg[cur]) if (x != par && !visited[x]) dfs(x, cur);
ord.push_back(cur);
}
ll nxt[mxn][18], sum[mxn][18];
set<ll> all;
void calc(int cur, int par) {
visited[cur] = 1;
if (cur == par) {
for (int i = 0; i < 18; i++) nxt[cur][i] = cur, sum[cur][i] = 0;
}
else {
nxt[cur][0] = par;
sum[cur][0] = 1;
for (int i = 1; i < 18; i++) {
int node = nxt[nxt[cur][i - 1]][i - 1];
nxt[cur][i] = node;
sum[cur][i] = sum[cur][i - 1] + sum[node][i - 1];
}
}
for (auto x : g[cur]) {
if (!visited[x]) calc(x, cur);
}
}
vector<Query> qr;
vector<string> res;
void solve(ll l, ll r, int IND) {
if (l == r) {
res.push_back("0");
return;
}
ll cur = l, ans = 1;
for (int i = 17; i >= 0; i--) {
ll nxtCur = nxt[cur][i];
if (v[nxtCur].second <= v[r].first) {
ans += sum[cur][i];
cur = nxtCur;
}
}
if (v[cur].second > v[r].second) {
res.push_back("impossible");
return;
}
if (v[r].first <= v[cur].second && v[cur].second <= v[r].second) {
res.push_back(to_string(ans));
return;
}
ans++;
res.push_back("impossible");
qr.push_back({v[cur].first, v[cur].second, v[r].first, v[r].second, ans, IND});
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
v.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v[i].first >> v[i].second;
all.insert(v[i].first);
all.insert(v[i].second);
}
ll cnt = 0;
map<ll, ll> h;
for (auto x : all) h[x] = cnt++;
for (int i = 1; i <= n; i++) {
v[i].first = h[v[i].first];
v[i].second = h[v[i].second];
}
for (int i = 1; i <= n; i++) sgt.update(1, 0, cnt - 1, v[i].first, v[i].second, i);
for (int i = 1; i <= n; i++) {
Node ans = sgt.get(1, 0, cnt - 1, v[i].second);
dg[i].push_back(ans.ind);
g[i].push_back(ans.ind);
g[ans.ind].push_back(i);
}
for (int i = 1; i <= n; i++) if (!visited[i]) dfs(i);
memset(visited, 0, sizeof(visited));
for (auto x : ord) if (!visited[x]) calc(x, x);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
solve(l, r, i);
}
vector<ll> ADD[cnt + 10];
vector<pair<ll, pair<ll, ll>>> GET[cnt + 10];
for (int i = 0; i < qr.size(); i++) {
auto x = qr[i];
ADD[x.l1].push_back(x.r1);
GET[x.r1].push_back({x.l2, {x.r2, i}});
}
for (int i = 0; i < cnt; i++) {
for (auto x : ADD[i]) con.update(1, 0, cnt - 1, x, i);
for (auto x : GET[i]) {
ll ind = con.get(1, 0, cnt - 1, x.first, x.second.first);
if (ind >= qr[x.second.second].l1) res[qr[x.second.second].ind] = to_string(qr[x.second.second].ans);
}
}
for (int i = 0; i < q; i++) cout << res[i] << endl;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:211:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
211 | for (int i = 0; i < qr.size(); i++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
97616 KB |
Output is correct |
| 2 |
Incorrect |
292 ms |
157000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
97620 KB |
Output is correct |
| 2 |
Correct |
42 ms |
97620 KB |
Output is correct |
| 3 |
Incorrect |
39 ms |
98136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
97620 KB |
Output is correct |
| 2 |
Correct |
42 ms |
97620 KB |
Output is correct |
| 3 |
Incorrect |
39 ms |
98136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
97620 KB |
Output is correct |
| 2 |
Correct |
42 ms |
97620 KB |
Output is correct |
| 3 |
Incorrect |
39 ms |
98136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
157000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
97616 KB |
Output is correct |
| 2 |
Incorrect |
292 ms |
157000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
