/*
ID: Victor Chen [mail_vi1]
PROG: Overtaking
LANG: C++
*/

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include "overtaking.h"
#include <cassert>

#define lson x<<1
#define rson x<<1|1

using namespace std;

typedef long long ll;

map<ll, int> mp;

const int Maxn = 1000;

class SegTreeMin
{
    public:
        struct Node
        {
            int l, r;
            int val, lazy;
        }p[8*Maxn*Maxn+10];

        void buildtree(int x, int l, int r)
        {
            p[x].l = l, p[x].r = r;
            if(p[x].l == p[x].r)
            {
                p[x].val = p[x].lazy = 0;
                return;
            }

            int mid = (l+r)/2;
            buildtree(lson, l, mid);
            buildtree(rson, mid+1, r);

            p[x].val = max(p[lson].val, p[rson].val);
        }

        void pushdown(int x)
        {
            if(p[x].lazy == 0)
                return;
            if(p[x].l == p[x].r)
            {
                p[x].lazy = 0;
                return;
            }

            p[lson].val = max(p[lson].val, p[x].lazy);
            p[lson].lazy = max(p[lson].lazy, p[x].lazy);

            p[rson].val = max(p[rson].val, p[x].lazy);
            p[rson].lazy = max(p[rson].lazy, p[x].lazy);

            p[x].lazy = 0;
        }

        void modify(int x, int l, int r, int k)
        {
            pushdown(x);
            if(l <= p[x].l && p[x].r <= r)
            {
                p[x].val = max(p[x].val, k);
                p[x].lazy = max(p[x].lazy, k);
                return;
            }
            
            if(l <= p[lson].r) modify(lson, l, r, k);
            if(p[rson].l <= r) modify(rson, l, r, k);

            p[x].val = max(p[lson].val, p[rson].val);
        }

        int query(int x, int l, int r)
        {
            pushdown(x);
            if(l <= p[x].l && p[x].r <= r)
                return p[x].val;
            
            int ret = 0;
            if(l <= p[lson].r) ret = max(ret, query(lson, l, r));
            if(p[rson].l <= r) ret = max(ret, query(rson, l, r));

            return ret;
        }
}tree;

struct Ranges
{
    ll l, r;
}p[Maxn+10][Maxn+10];

int n, m;
ll dis[Maxn+10], spd[Maxn+10];

int cnt, cnt2;
ll st[2*Maxn*Maxn+10], mst[2*Maxn*Maxn*2];

struct Node
{
    int id;
    ll bg, ed;

    bool operator < (const Node &x) const
    {
        return x.bg < bg;
    }

    Node(){}
    Node(int id, ll bg, ll ed)
    {
        this->id = id;
        this->bg = bg, this->ed = ed;
    }
};
priority_queue<Node> q;

struct Pair
{
    ll bg, ed;
    bool operator < (const Pair &x) const
    {
        if(x.ed != ed)
            return x.ed < ed;
        else
            return x.bg < bg;
    }
    Pair(){}
    Pair(ll bg, ll ed)
    {
        this->bg = bg; this->ed = ed;
    }
};
priority_queue<Pair> pq;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
    // Pre-processing everything.
    m = M-1;
    for(int i=0; i<M; i++)
        dis[i] = S[i];

    spd[0] = X;
    for(int i=0; i<N; i++)
    {
        W[i] -= X;
        if(W[i] <= 0)
            continue;
        
        spd[++n] = W[i];
        q.push(Node(n, T[i], T[i] + dis[1] * spd[n]));
    }

    if(n == 0)
        return;

    ll cur = -1, curmx = 0, mx = 0;
    while(!q.empty())
    {
        Node tp = q.top();
        q.pop();

        if(tp.bg == cur)
            curmx = max(curmx, tp.ed);
        else
        {
            mx = max(mx, curmx);
            curmx = tp.ed;
            cur = tp.bg;
        }

        p[tp.id][1].l = tp.bg;
        p[tp.id][1].r = max(mx, tp.ed);
    }

    // for(int i=1; i<=n; i++)
    //     printf("%lld %lld\n", p[i][1].l, p[i][1].r);

    for(int i=2; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
            q.push(Node(j, p[j][i-1].r, p[j][i-1].r + (dis[i]-dis[i-1]) * spd[j]));
        
        cur = 0, curmx = 0, mx = 0;
        while(!q.empty())
        {
            Node tp = q.top();
            q.pop();

            if(tp.bg == cur)
                curmx = max(curmx, tp.ed);
            else
            {
                mx = max(mx, curmx);
                curmx = tp.ed;
                cur = tp.bg;
            }

            p[tp.id][i].l = tp.bg;
            p[tp.id][i].r = max(mx, tp.ed);
        }
    }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            st[++cnt] = p[i][j].l;
            st[++cnt] = p[i][j].r;

            // printf("%d %d\n", st[cnt-1], st[cnt]);
        }
    sort(st+1, st+cnt+1);

    st[0] = -1;
    for(int i=1; i<=cnt; i++)
        if(st[i] != st[i-1])
        {
            mp[st[i]] = ++cnt2;
            mst[cnt2] = st[i];
        }
    
    // printf("%d\n", cnt2);

    tree.buildtree(1, 1, cnt2);

    // Consider the ending case.
    for(int i=1; i<=n; i++)
    {
        // printf("%d %d\n", mp[p[i][m].l], mp[p[i][m].r]);
        tree.modify(1, mp[p[i][m].l]+1, mp[p[i][m].r], mp[p[i][m].r]);

        // printf("%d\n", tree.query(1, 129, 129));
    }
    
    for(int i=m-1; i>=1; i--)
    {
        for(int j=1; j<=n; j++)
            pq.push(Pair(p[j][i].l, p[j][i].r));
        
        ll pred = 0, preb = 0;
        while(!pq.empty())
        {
            Pair tp = pq.top();
            pq.pop();

            if(tp.ed == pred)
            {
                // assert(tp.bg >= preb);
                preb = tp.bg;
                continue;
            }
            else
                pred = tp.ed, preb = tp.bg;
            
            // printf("%lld %lld %lld\n", mp[tp.bg]+1, mp[tp.ed], max(tree.query(1, mp[tp.ed], mp[tp.ed]), mp[tp.ed]));
            tree.modify(1, mp[tp.bg]+1, mp[tp.ed], max(tree.query(1, mp[tp.ed], mp[tp.ed]), mp[tp.ed]));
        }
    }

    // for(int i=1; i<=cnt2; i++)
    //     printf("%d ", tree.query(1, i, i));
    // printf("\n");
}

ll arrival_time(ll Y)
{
    int l = 1, r = cnt2, ans = cnt2+1;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(Y <= mst[mid])
        {
            r = mid - 1;
            ans = mid;
        }
        else
            l = mid + 1;
    }

    // printf("Check: %lld, [%lld, %lld]\n", ans, mst[ans-1], mst[ans]);

    if(ans == cnt2+1) return Y+spd[0]*dis[m];
    else
    {
        ll ed = tree.query(1, ans, ans);
        if(ed == 0)
        {
            // printf("Check %lld\n", Y);
            return Y + spd[0] * dis[m];
        }
        else
        {
            printf("Check %lld\n", ed);
            return mst[ed] + spd[0] * dis[m];
        }
    }
}

// int main()
// {
//     int L = 20, N = 4;
//     vector<ll> T; T.clear();
//     T.push_back(10); T.push_back(10); T.push_back(20); T.push_back(25);
//     vector<int> W; W.clear();
//     W.push_back(2); W.push_back(1); W.push_back(3); W.push_back(1);
//     int X = 0, M = 2;
//     vector<int> S; S.clear();
//     S.push_back(0); S.push_back(20);
//     // for(int i=0; i<=20; i++) S.push_back(i);

//     init(L, N, T, W, X, M, S);
//     printf("%lld\n", arrival_time(3));

//     return 0;
// }