#include "infection.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define ll long long
using namespace std;
const int N=2e5+5;

vector<int> solve(vector<pair<int,int>> ed, vector<ll> d,
                  vector<int> s, vector<int> t, vector<bool> is)
{
    int n=d.size();
    vector<pair<ll,int>> swep;
    for(int i=0;i<n;++i)
    {
        swep.eb(d[i],i);
        swep.eb(d[i]+t[i]-s[i]+1,-i);
    }
    sort(swep.begin(),swep.end());
    vector<int> ans(n);
    map<ll,vector<ll>> jos,sus;
    map<ll,int> cjos,csus;
    for(auto [x,i]:swep)
    {
        if(i>0)
        {
            if(cjos[d[i]-s[i]]!=0) is[i]=1;
            if(csus[d[i]+s[i]]!=0) is[i]=1;
            if(s[i]<=t[i]) ++cjos[d[i]-s[i]];
            else ++csus[d[i]+s[i]];
            if(is[i])
            {
                if(cjos[d[i]-s[i]]!=0) jos[d[i]-s[i]].pb(d[i]);
                if(csus[d[i]+s[i]]!=0) sus[d[i]+s[i]].pb(d[i]);
            }
        }
        else
        {
            i*=-1;
            if(s[i]<=t[i]) --cjos[d[i]-s[i]];
            else --csus[d[i]+s[i]];
            if(is[i])//de la inceput infectat
            {
                ans[i]=abs(t[i]-s[i])+1;
            }
            else if(s[i]<=t[i])
            {
                auto it=lower_bound(jos[d[i]-s[i]].begin(),jos[d[i]-s[i]].end(),d[i]);
                if(it!=jos[d[i]-s[i]].end()&&(*it)<=d[i]+t[i]-s[i])
                {
                    ans[i]=d[i]+t[i]-s[i]-(*it)+1;
                }
            }
            else
            {
                auto it=lower_bound(sus[d[i]+s[i]].begin(),sus[d[i]+s[i]].end(),d[i]);
                if(it!=sus[d[i]+s[i]].end()&&(*it)<=d[i]+s[i]-t[i])
                {
                    ans[i]=d[i]+s[i]-t[i]-(*it)+1;
                }
            }
        }
    }
    return ans;
}
