#include<bits/stdc++.h>
#include "infection.h"
#include <vector>
#include <utility>
using namespace std;
struct lines
{
    int idx=0;
    double m,k;
    int s,t;
    long long da;
    bool dot;
    lines(){};
    lines(int st,int f,int d,int id)
    {
        idx=id;
        int x1=st;
        int x2=st+1;
        long long y1=d;
        long long y2=d;
        da=d;
        if(st<f)y2++;
        else y2--;
        if(st==f)dot=1;
        k=(double)(y2-y1)/(double)(x2-x1);
        m=y1+k*x1;
        s=st;
        t=f;
    }
};
int inters(lines a,lines b)
{
    if(a.dot)
    {
        swap(a,b);
        if(b.s>=a.s&&b.s<=a.t&&b.da==a.da)return b.s;
        return -1;
    }
    if(a.k==b.k)return -1;
    int x=b.m-a.m;
    int y=a.k-b.k;
    if(x%y)return -1;
    int h=(double)x/(double)y;
    if(h>=a.s&&h<=a.t&&h>=b.s&&h<=b.t)return h;
    return -1;
}
bool cmp(lines a,lines b)
{
    if(a.s==b.s)return a.t<b.t;
    return a.s<b.s;
}
int m;
vector<lines>in;
vector<lines>s;
std::vector<int> solve(
    std::vector<std::pair<int, int>> R,
    std::vector<long long> D,
    std::vector<int> S,
    std::vector<int> T,
    std::vector<bool> I
)
{
    m=D.size();
    vector<int>ans;
    ans.assign(m,0);
    for(int i=0;i<m;i++)
    {
        if(I[i])
        {
            in.push_back({S[i],T[i],D[i],i});
            ans[i]=abs(T[i]-S[i])+1;
        }
        else s.push_back({S[i],T[i],D[i],i});
    }
    sort(s.begin(),s.end(),cmp);
    for(int i=0;i<s.size();i++)
    {
        for(int j=0;j<in.size();j++)
        {
            int h=inters(s[i],in[j]);
            if(h==-1)continue;
            ans[s[i].idx]=abs(h-s[i].t)+1;
            in.push_back({h,s[i].t,s[i].m+h*s[i].k,i});
        }
    }
    return ans;
}
