#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define all(v) v.begin(),v.end()
#define sz(s) ((int)s.size())
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
const ll inf=1e18;
const int MAX=1e5+10;
const int MX=1e8;
const int mod=1e9+7;
int binpow(int a,int n){
if(!n)return 1;
if(n%2==1)return a*binpow(a,n-1)%mod;
int k=binpow(a,n/2);
return k*k%mod;
}
int n,m;
int s[MAX],f[MAX];
int dp[MAX][4];
int pr[MAX][4];
vector<int> vf;
bool check(int k){
memset(dp,-1,sizeof(dp));
memset(pr,-1,sizeof(pr));
if(f[1]>=s[1])dp[1][0]=s[1]+k;
if(f[1]>=s[1]-k)dp[1][3]=s[1];
{
if(s[2]-s[1]<=k){
bool ok=1;
for(int i=1;i<=m;i++){
if(f[i]<=s[2]){
if(!((s[2]-k<=f[i]&&f[i]<=s[2])||(s[1]<=f[i]&&f[i]<=s[1]+k)))ok=0;
}
}
if(ok)dp[2][1]=max(s[2],s[1]+k);
}
}
{
bool ok=1;
for(int i=1;i<=m;i++){
if(f[i]<=s[2]){
if(!((s[2]-k<=f[i]&&f[i]<=s[2])||(s[1]-k<=f[i]&&f[i]<=s[1])))ok=0;
}
}
if(ok)dp[2][2]=s[2];
}
{
bool ok=1;
for(int i=1;i<=m;i++){
if(f[i]<=s[2]){
if(!(s[1]<=f[i]&&f[i]<=s[1]+k||s[2]==f[i]))ok=0;
}
}
if(ok)dp[2][0]=s[2]+k,pr[2][0]=0;
}
// cout<<dp[1][0]<<" "<<dp[1][1]<<" "<<dp[1][2]<<" "<<dp[1][3]<<"\n";
// cout<<dp[2][0]<<" "<<dp[2][1]<<" "<<dp[2][2]<<"\n";
for(int i=3;i<=n;i++){
for(int j=0;j<4;j++){
int k=i-1;
if(dp[k][j]!=-1)if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i]){
if(max(dp[k][j],s[i]+k)>dp[i][0]){
pr[i][0]=j;
dp[i][0]=max(dp[k][j],s[i]+k);
}
}
if(dp[k][j]!=-1){
if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i]-k){
if(max(dp[k][j],s[i]+k)>dp[i][3]){
pr[i][3]=j;
dp[i][3]=max(dp[k][j],s[i]+k);
}
}
}
k--;
if(dp[k][j]==-1)continue;
if(s[i]-s[i-1]>k){
if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i-1]){
if(ub(all(vf),max(dp[k][j],s[i-1]+k))==vf.end()||vf[ub(all(vf),max(dp[k][j],s[i-1]+k))-vf.begin()]>=s[i]-k){
if(max(dp[k][j],s[i])>dp[i][1]){
pr[i][1]=j;
dp[i][1]=max(dp[k][j],s[i]);
}
}
}
}
else{
if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i]-k){
if(max(dp[k][j],s[i-1]+k)>dp[i][1]){
pr[i][1]=j;
dp[i][1]=max(dp[k][j],s[i-1]+k);
}
}
}
if(s[i]-s[i-1]>k){
if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i-1]-k){
if(ub(all(vf),max(dp[k][j],s[i-1]))==vf.end()||vf[ub(all(vf),max(dp[k][j],s[i-1]))-vf.begin()]>=s[i]-k){
if(max(dp[k][j],s[i])>dp[i][1]){
pr[i][2]=j;
dp[i][2]=max(dp[k][j],s[i]);
}
}
}
}
else{
if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i-1]-k){
if(max(dp[k][j],s[i-1]+k)>dp[i][1]){
pr[i][2]=j;
dp[i][2]=max(dp[k][j],s[i]);
}
}
}
}
// cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<"\n";
}
for(int j=0;j<4;j++)if(dp[n][j]>=f[n])return 1;
return 0;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=1;i<=m;i++){
cin>>f[i];
vf.pb(f[i]);
}
// check(6);
int l=0,r=2e9,res=-1;
while(l<=r){
int m=(l+r)/2;
if(check(m)){
r=m-1;
res=m;
}
else l=m+1;
}
cout<<res<<"\n";
if(res!=-1){
check(res);
int a=n,b=-1;
string s;
for(int k=0;k<3;k++)if(dp[n][k]>=f[n])b=k;
while(a>0){
if(b==0){
b=pr[a][b];
a--;
s.pb('R');
}
else if(b==1){
b=pr[a][b];
a-=2;
s.pb('L');
s.pb('R');
}
else if(b==2){
b=pr[a][b];
a-=2;
s.pb('L');
s.pb('L');
}
else{
b=pr[a][b];
a--;
s.pb('L');
}
}
reverse(all(s));
cout<<s<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
}
Compilation message
Main.cpp: In function 'bool check(long long int)':
Main.cpp:66:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
66 | if(!(s[1]<=f[i]&&f[i]<=s[1]+k||s[2]==f[i]))ok=0;
| ~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6736 KB |
Correct |
| 2 |
Incorrect |
6 ms |
6804 KB |
User solution is incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
6804 KB |
User solution is incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6736 KB |
Correct |
| 2 |
Incorrect |
38 ms |
8396 KB |
User solution is worse than jury's solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6736 KB |
Correct |
| 2 |
Incorrect |
6 ms |
6804 KB |
User solution is incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6736 KB |
Correct |
| 2 |
Incorrect |
212 ms |
8496 KB |
User solution is worse than jury's solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6736 KB |
Correct |
| 2 |
Incorrect |
6 ms |
6804 KB |
User solution is incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
