#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 mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pw(x) (1LL << (x))
using namespace std;
mt19937_64 rng(228);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
bool umn(T& a, T b) {
return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
return a < b ? a = b, 1 : 0;
}
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
const int N = 1e5 + 5;
int n, q;
pii a[N];
ve<int> order;
int to[N];
int d[N];
ve<pii> Q[N];
int ans[N];
bool subtask1 = 1;
pii get(int v) {
if (to[v] == v) {
return {v, 0};
} else {
pii p = get(to[v]);
p.se += d[v];
to[v] = p.fi;
d[v] = p.se;
return {p.fi, p.se};
}
}
bool TL() {
return (double)clock() / CLOCKS_PER_SEC > 1.4;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> n >> q;
// subtask1 &= n > 5000 || q > 100;
ve<int> u;
fr (i, 1, n) {
cin >> a[i].fi >> a[i].se;
order.pb(i);
u.pb(a[i].se);
}
sort(all(u));
// fr (i, 1, n) {
// int p1 = lower_bound(all(u), a[i].fi) - u.begin();
// int p2 = upper_bound(all(u), a[i].se) - u.begin() - 1;
// if (max(0, p2 - p1 + 1) > 2) {
// assert(0);
// }
// }
// fr (i, 1, n) {
// int cnt = 0;
// fr (j, 1, n) {
// if (i == j) continue;
//
// if (a[j].fi <= a[i].se && a[i].se <= a[j].se) {
// cnt++;
// }
// }
// assert(cnt <= 1);
// }
fr (i, 1, q) {
int s, e;
cin >> s >> e;
if (s == e) {
ans[i] = 0;
continue;
}
if (a[s].se >= a[e].fi && a[s].se <= a[e].se) {
ans[i] = 1;
continue;
}
if (a[s].se > a[e].se) {
ans[i] = -1;
continue;
}
Q[e].pb({s, i});
}
sort(all(order), [](int i, int j) {
return a[i].se < a[j].se || (a[i].se == a[j].se && a[i].fi < a[j].fi);
});
fr (i, 1, n) {
to[i] = i;
d[i] = 0;
}
subtask1 = 1;
ve<pii> add, del;
fr (idx, 0, sz(order) - 1) {
int i = order[idx];
int l = 0;
int r = idx - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
int j = order[mid];
if (a[j].se < a[i].fi) {
l = mid + 1;
} else {
r = mid;
}
}
if (l <= idx - 1 && a[order[l]].se >= a[i].fi) {
add.pb({l, i});
del.pb({idx, i});
}
// rf (ptr, idx - 1, 0) {
// int j = order[ptr];
// if (a[j].se < a[i].fi) {
// break;
// }
//
// subtask1 &= ptr == idx - 1;
// to[j] = i;
// d[j] = 1;
// }
if (sz(Q[i])) {
sort(all(add));
sort(all(del));
int ptr1 = 0;
int ptr2 = 0;
set<int> s;
fr (cur, 0, idx) {
while (ptr1 < sz(add) && add[ptr1].fi <= cur) {
s.insert(add[ptr1].se);
ptr1++;
}
while (ptr2 < sz(del) && del[ptr2].fi <= cur) {
s.erase(del[ptr2].se);
ptr2++;
}
int i = order[cur];
if (sz(s)) {
d[i] = 1;
to[i] = *s.rbegin();
}
}
add.clear();
del.clear();
}
fe (cur, Q[i]) {
int v = cur.fi;
int sum = 0;
while (to[v] != v) {
sum += d[v];
v = to[v];
}
// cout << "YEP " << i << "\n";
// cout << "start " << cur.fi << "\n";
// cout << "to: " << to[cur.fi] << "\n";
if (v == i) {
ans[cur.se] = sum;
} else {
ans[cur.se] = -1;
}
}
}
fr (i, 1, q) {
if (ans[i] == -1) {
cout << "impossible\n";
} else {
cout << ans[i] << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Execution timed out |
1575 ms |
8180 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1587 ms |
8104 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Execution timed out |
1575 ms |
8180 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
