PROG-T1052: Domino

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;

int coor[N + 2], height[N + 2], dp[N + 2], pr[N + 1];

int main(){

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d", &coor[i], &height[i]);
    }
    int mx = 0;
    int idx = 0;
    char dir = 'L';
    // Left side
    dp[n + 1] = 1e9 + 1;
    for(int i = n; i >= 1; --i){
        if(dp[i + 1] < coor[i]){
            dp[i] = min(dp[i + 1], coor[i] - height[i]);
            pr[i] = pr[i + 1];
        } else {
            dp[i] = coor[i] - height[i];
            pr[i] = i;
        }
        int cnt = pr[i] - i + 1;
        if(cnt > mx){
            mx = cnt;
            idx = pr[i];
            dir = 'L';
        } else if(cnt == mx && pr[i] < idx){
            idx = pr[i];
            dir = 'L';
        }
    }
    // Right Side
    dp[0] = -1;
    for(int i = 1; i <= n; ++i){
        if(dp[i - 1] > coor[i]){
            dp[i] = max(dp[i - 1], coor[i] + height[i]);
            pr[i] = pr[i - 1];
        } else {
            dp[i] = coor[i] + height[i];
            pr[i] = i;
        }
        int cnt = i - pr[i] + 1;
        if(cnt > mx){
            mx = cnt;
            idx = pr[i];
            dir = 'R';
        } else if(cnt == mx && pr[i] < idx){
            idx = pr[i];
            dir = 'R';
        }
    }
    cout << idx << ' ' << dir;

    return 0;
}