이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
#define int long long
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 12;
const int mod = 1e9 + 7;
vector<int> g[maxn];
int d[maxn];
int up[20][maxn];
int ans[5005][5005];
int l[maxn], r[maxn];
int n, q;
void solve5000(vector<pair<int, int>> u) {
for(int j = 1; j <= n; j++) {
pair<int, int> mx = {-1, -1};
for(auto [x, pos] : u) {
if(pos < 0) {
if(r[-pos] > r[j]) continue;
mx = max(mx, {r[-pos], -pos});
}
else {
if(r[pos] > r[j]) continue;
g[mx.second].push_back(pos);
}
}
queue<int> q;
for(int i = 1; i <= n; i++) {
ans[i][j] = 1e9;
}
ans[j][j] = 0;
q.push(j);
for(int i = 1; i <= n; i++) {
if(r[i] >= l[j] && r[i] <= r[j] && i != j) {
q.push(i);
ans[i][j] = 1;
}
}
while(q.size()) {
int v = q.front();
q.pop();
for(int to : g[v]) {
if(ans[to][j] > ans[v][j] + 1) {
ans[to][j] = ans[v][j] + 1;
q.push(to);
}
}
}
for(int i = 1; i <= n; i++) {
g[i].clear();
}
}
while(q--) {
int i, j;
cin >> i >> j;
if(ans[i][j] > n) {
cout << "impossible\n";
}
else {
cout << ans[i][j] << ent;
}
}
}
void solve() {
cin >> n >> q;
vector<pair<int, int>> u;
for(int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
u.push_back({l[i], -i});
u.push_back({r[i], i});
}
sort(u.begin(), u.end());
if(n <= 5000) {
solve5000(u);
return;
}
while(q--) {
int i, j;
cin >> i >> j;
if(r[i] > r[j]) {
cout << "impossible\n";
continue;
}
if(i == j) {
cout << "0\n";
continue;
}
int ans = 0;
pair<int, int> mx = {-1, -1};
for(auto [x, pos] : u) {
if(pos < 0) {
if(r[-pos] > r[j]) continue;
mx = max(mx, {r[-pos], -pos});
}
else {
up[0][pos] = mx.second;
}
}
for(int _ = 0; _ <= n && r[i] < l[j]; _++) {
ans++;
i = up[0][i];
}
if(ans > n) {
cout << "impossible\n";
}
else {
if(i != j) ans++;
cout << ans << ent;
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |