### Jenil2910's blog

By Jenil2910, history, 10 months ago, ,

I was solving 1175E using the path compression technique as decribed here, but I was unable to figure out why I am getting TLE.

My code:

#include<bits/stdc++.h>

#define vi vector<int>
#define vii vector<pair<int,int>>
#define pii pair<int, int>
#define loop(i,s,n) for(int i=s;i<n;i++)
#define ft first
#define sd second

using namespace std;

#define N (int)5e5+10

pii dp[N];

int main(){
int n,m;
cin>>n>>m;

vii a(n), q(m);
loop(i, 0, n) cin>>a[i].ft>>a[i].sd;
loop(i, 0, m) cin>>q[i].ft>>q[i].sd;

sort(a.begin(), a.end());
int cur=0;
pii mx={0, -1};
loop(i, 0, N){
while(cur<n && a[cur].ft<=i){
mx = max(mx, {a[cur].sd, a[cur].ft});
cur++;
}
if(mx.ft<=i){
dp[i] = {-1, -1};
}else{
dp[i] = {mx.ft, 1};
}
}
/*
*/

vi idx(m), ANS(m);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [q](int a, int b){return q[a].sd<q[b].sd;});

for(auto i: idx){
queue<int> qu;

int s=q[i].ft, ans=0;
while(s<q[i].sd){
if(dp[s].ft==-1){
s=-1, ans=-1;
break;
}else{
qu.push(s);
ans+=dp[s].sd, s=dp[s].ft;
}
}

ANS[i]=ans;

while(!qu.empty()){
int t=qu.front();
qu.pop();

if(s==-1){
dp[t] = {-1, -1};
}else{
int old=dp[t].sd;
dp[t] = max(dp[t], pii(s, ans));
ans-=old;
}
}
}

loop(i, 0, m){
cout<<ANS[i]<<endl;
}

// loop(i, 0, a[n-1].sd){
// cout<<i<<" "<<dp[i].ft<<" "<<dp[i].sd<<endl;
// }

return 0;
}


For each index, I am basically storing farthest index reachable and minimum no. of steps corresponding to it. Then I process queries in increasing order of last index, and compress the path taken after each query.

Can you help me find what am I missing?

• -3