#include "infection.h"
#include <vector>
#include <iostream>
#include <map>
#include <utility>

#define ll long long

#define nMax 150000
#define infMax 10000000

using namespace std;

struct nod{
    vector<int> prezenti;
};

struct zi{
    map<int, nod> orase;
};

map<int, zi> zile;

vector<int> solve(
    vector<pair<int, int>> R,
    vector<ll> cameAt,
    vector<int> start,
    vector<int> stop,
    vector<bool> inf
) {
    int n = cameAt.size();
    vector<int> infDate;
    vector<bool> mergeInvers;
    infDate.resize(n);
    mergeInvers.resize(n);

    for(int i=0;i<n;i++){
        if(inf[i])infDate[i]=cameAt[i];
        else infDate[i]=infMax;
    }

    for(int i=0;i<n;i++){
        int dir, pos=start[i];
        ll curTime=cameAt[i];
        if(start[i]<stop[i]){dir=1;mergeInvers[i]=false;}
        else{
          dir=-1;
          mergeInvers[i]=true;
        }

        do{
            zile[curTime].orase[pos].prezenti.push_back(i);
            curTime++;
            pos+=dir;
        }while((pos!=stop[i]));

    }

    for(auto it : zile){
        for(auto jt : it.second.orase){
            bool infPrezent=0;
            for(auto kt : jt.second.prezenti)
                if(infDate[kt]<=it.first)
                    {infPrezent=true; break;}
            if(infPrezent)
                for(auto kt : jt.second.prezenti)
                    if(infDate[kt]==infMax) infDate[kt]=it.first;
        }

    }

    for(int i=0;i<n;i++){
        if(infDate[i]==infMax)continue;
        else if(!mergeInvers[i])infDate[i]=cameAt[i]+(stop[i]-start[i])-infDate[i];
        else infDate[i]=abs(cameAt[i]+(stop[i]-start[i])-infDate[i]);
    }

    return infDate;
}
