Jenil2910's blog

By Jenil2910, history, 5 years ago, In English

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?

  • Vote: I like it
  • -3
  • Vote: I do not like it