#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,m,a;
vector<ll>v1,v2;
ll dp[100007][2];
ll pop[100007][2];
bool last;//1 to prawo
bool czy(ll x){
ll ak=0;
for(ll i=0;i<n;i++){
vector<ll>v;
for(;ak<v2.size() && v2[ak]<v1[i];ak++){
v.pb(v2[ak]);
}
v.pb(v1[i]);
if(!i){
dp[0][0]=0;
if(v[0]+x<v1[i])dp[0][0]=-INFL;
dp[0][1]=v1[i]-v[0];
}
else{
dp[i][0]=-INFL;
dp[i][1]=INFL;
pop[i][0]=1;
pop[i][1]=0;
if(dp[i-1][1]+v1[i]-v1[i-1]<=x || (dp[i-1][1]==0 && *lower_bound(v.begin(),v.end(),v1[i-1]+1)+x>=v1[i]))dp[i][0]=max(0LL,max(dp[i][0],x-v1[i]+v1[i-1]));
if(v[0]+x>=v1[i]){dp[i][0]=max(0LL,max(dp[i][0],dp[i-1][0]-v1[i]+v1[i-1]));
if(dp[i][0]==max(0LL,dp[i-1][0]-v1[i]+v1[i-1]))pop[i][0]=0;
}
dp[i][1]=min(dp[i][1],max(dp[i-1][1]+v1[i]-v1[i-1],v1[i]-v[0]));
if(dp[i][0]>=0)dp[i][1]=min(dp[i][1],v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+1+dp[i-1][0]));
if(dp[i][0]==max(dp[i-1][1]+v1[i]-v1[i-1],v1[i]-v[0]))pop[i][1]=1;
}
}
if(v2.back()-v1.back()-dp[n-1][0]<=0){
last=0;
return 1;
}
if(v2.back()-v1.back()<=x && dp[n-1][1]==0){
last=1;
return 1;
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(ll i=0;i<n;i++){
cin>>a;
v1.pb(a);
}
for(ll i=0;i<m;i++){
cin>>a;
if(*lower_bound(v1.begin(),v1.end(),a)==a)continue;
v2.pb(a);
}
ll pocz=0;
ll kon=INFL/5;
while(pocz!=kon){
ll mid=(pocz+kon)/2;
if(czy(mid))kon=mid;
else pocz=mid+1;
}
if(kon==INFL/5){
cout<<-1;return 0;
}
cout<<kon<<"\n";
string s;
for(ll i=0;i<n;i++){
if(last)s.pb('R');
else s.pb('L');
last=pop[n-1-1][last];
}
reverse(s.begin(),s.end());cout<<s;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |