PROG-1052: Domino

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 1e5 + 10;
int X[N], H[N], dp[3][N]; /// 1 r, 2 l
vector < vector <int>> tree(3, vector <int> (1 << 19, -INF));
int n;

int Update(int idx, int l, int r, int side, int pst, int val){
    if(l == r) return tree[side][idx] = val;
    int mid = (l + r) / 2;
    if(pst <= mid)
        return tree[side][idx] = max( Update(2 * idx, l, mid, side, pst, val), tree[side][2 * idx + 1] );
    return tree[side][idx] = max( tree[side][2 * idx], Update(2 * idx + 1, mid + 1, r, side, pst, val) );
}

int Query(int idx, int l, int r, int side, int s, int e){
    if(r < s or l > e) return -INF;
    if(s <= l and r <= e) return tree[side][idx];
    int mid = (l + r) / 2;
    return max( Query(2 * idx, l, mid, side, s, e), Query(2 * idx + 1, mid + 1, r, side, s, e) );
}

int MaxPst(int l, int val){
    int r = n, mx = l;
    while(l <= r){
        int mid = (l + r) / 2;
        if(val > X[mid]) mx = max(mx, mid), l = mid + 1;
        else r = mid - 1;
    }
    return mx;
}

int MinPst(int r, int val){
    int l = 1, mn = r;
    while(l <= r){
        int mid = (l + r) / 2;
        if(val < X[mid]) mn = min(mn, mid), r = mid - 1;
        else l = mid + 1;
    }
    return mn;
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        scanf("%d%d", &X[i], &H[i]);
    }

    /// r
    for(int i=n;i>=1;i--){
        int s = i;
        int e = MaxPst(i, X[i] + H[i]);
        if(e - s + 1 == 1) dp[1][i] = 1;
        else dp[1][i] = Query(1, 1, n, 1, s, e) - i;
        Update(1, 1, n, 1, i, dp[1][i] + i);
    }

    /// l
    for(int i=1;i<=n;i++){
        int s = MinPst(i, X[i] - H[i]);
        int e = i;
        if(e - s + 1 == 1) dp[2][i] = 1;
        else dp[2][i] = Query(1, 1, n, 2, s, e) + i;
        Update(1, 1, n, 2, i, dp[2][i] - i);
    }

    int mxR = 0, pstR = 0, mxL = 0, pstL = 0;
    for(int i=1;i<=n;i++){
        if(dp[1][i] > mxR) mxR = dp[1][i], pstR = i;
        if(dp[2][i] > mxL) mxL = dp[2][i], pstL = i;
    }

    if(mxR > mxL) printf("%d R", pstR);
    else if(mxL > mxR) printf("%d L", pstL);
    else if(pstL == pstR) printf("%d L", pstL); /// mxl == mxr
    else if(pstL < pstR) printf("%d L", pstL);
    else printf("%d R", pstR);

    return 0;
}