#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ll int
//~ #define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 2000010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N,Q;
int S[maxn],E[maxn],s,e;
vpii queries[maxn];
const int sqrtn = 1000;
vi A[maxn];
vi adj[maxn];
int par[maxn], twok[maxn][21];
bool vis[maxn];
struct node{
int s,e,m;
pi val = pi(INF,INF), lazy=pi(INF,INF);
node *l,*r;
node(int ss,int ee){
s = ss; e = ee; m = (s + e) / 2;
if (s != e){
l = new node(s,m); r = new node(m+1,e);
}
}
void prop(){
if (s == e || lazy == pi(INF,INF)) return;
l->lazy = min(l->lazy, lazy); r->lazy = min(r->lazy, lazy);
l->val = min(l->val, lazy); r->val = min(r->val, lazy);
lazy = pi(INF,INF);
}
void upd(int a,int b,pi c){
prop();
if (a <= s && e <= b){
val = min(val, c); lazy = min(lazy, c);
}else if (a > e || s > b) return;
else{
l->upd(a,b,c); r->upd(a,b,c);
val = min(l->val, r->val);
}
}
pi qry(int a,int b){
prop();
if (a <= s && e <= b) return val;
else if (a > e || s > b) return pi(INF,INF);
else return min(l->qry(a,b), r->qry(a,b));
}
}*root;
void dfs(int x, int p){
twok[x][0] = p;
vis[x] = 1;
FOR(i,1,20){
if (twok[x][i-1] == -1) break;
twok[x][i] = twok[twok[x][i-1]][i-1];
}
aFOR(i,adj[x]) dfs(i,x);
}
int ans[maxn];
void solve(){
cin >> N >> Q;
vi v;
FOR(i,1,N){
cin >> S[i] >> E[i];
v.pb(S[i]); v.pb(E[i]);
}
sort(all(v)); v.erase(unique(all(v)), v.end());
FOR(i,1,N){
S[i] = lbd(v, S[i]) - v.begin() + 1;
E[i] = lbd(v, E[i]) - v.begin() + 1;
}
FOR(i,1,N) A[E[i]].pb(i);
//~ cout << A[7].size();
//~ return;
//~ FOR(i,1,N){
//~ cout << S[i] << ' ' << E[i] << '\n';
//~ }
//~ return;
//~ FOR(i,1,Q){
//~ cin >> s >> e;
//~ if (s == e) ans[i] = 0;
//~ else if (S[e] <= E[s] && E[s] <= E[e]) ans[i] = 1;
//~ else queries[E[e]].pb(pii(pi(s,e), i));
//~ }
root = new node(1,2*N);
//~ root->upd(1,1,pi(1,1
FOR(i,1,N) root->upd(S[i], E[i], pi(S[i], i));
FOR(i,1,N){
par[i] = root->qry(S[i], E[i]).s;
if (par[i] == i) par[i] = -1;
else adj[par[i]].pb(i);
cout << par[i] << ' ';
}
cout << '\n';
FOR(i,1,N) if (!vis[i]) dfs(i,-1);
FOR(i,1,Q){
cin >> s >> e;
if (s == e) cout << 0;
else if (S[e] <= E[s] && E[s] <= E[e]) cout << 1;
else{
int x = e, ans = 0;
DEC(k,20,0) if (twok[x][k] != -1 && S[twok[x][k]] > E[s]){
x = twok[x][k]; ans += (1<<k);
}
if (par[x] == -1) cout << "impossible";
else{
x = par[x];
if (S[x] <= E[s] && E[s] <= E[x]) cout << ans + 2;
else cout << x << ' ' << "impossible";
}
}
cout << '\n';
}
}
int32_t main(){
fast;
//~ cin >> TC;
//~ while (TC--) solve();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
141152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
141244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
141244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
141244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
919 ms |
187224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
141152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
