PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Abhinav Sharma
Tester: Satyam
Editorialist: Nishank Suresh
DIFFICULTY:
To be calculated
PREREQUISITES:
Sorting, prefix sums
PROBLEM:
There are N cans lying on the x-axis, the i-th at position X_i. The i-th can can be moved one step in either direction for a cost of B_i.
There is also a green zone, initially lying between position L and position R. You must pick an integer k and mirror the green zone about position k. Then, move some of the cans as you please. If the i-th can lies within the final green zone, it gives a profit of A_i.
Maximize the profit you obtain by performing these actions, where the profit is the sum of A_i of cans lying within the final green zone, minus the cost spent moving cans.
EXPLANATION:
Hint 1
Notice that no matter which k is chosen, L' and R must have the same parity. Can you further reduce the number of positions L' we need to consider?
Hint 2
It is enough to consider positions L' such that a can is initially present at at least one of the positions \{L'-1, L', L'+1, R'-1, R', R'+1\}.
Hint 3
Now use a sweepline!
Full solution
First, note that mirroring about the line X = k gives us L' = 2k - R and R' = 2k - L, which means L' and R always have the same parity. Conversely, any L' that has the same parity as R can be reached by choosing k = \frac{L' + R}{2}.
This halves the possibilities for our choice of L' — can we do any better?
It turns out, we can! It is enough to only consider those positions L' such that, for at least one 1 \leq i \leq N, X_i \in \{L'-1, L', L'+1, R', R'-1, R'+1\}.
Proof
Consider a position L' such that no can is initially present at any of \{L'-1, L', L'+1, R'-1, R', R'+1\}. After choosing this position L', we move some cans from the left of L' to position L' — let the sum of B_i of these cans be S_1. Similarly, we move some cans from the right of R' to R', let the sum of their B_i be S_2.
Without loss of generality, let S_1 \geq S_2. Consider what happens when we consider the position L' - 2 instead.
- Every can initially lying within the range [L', R'] still lies within [L'-2, R'-2], since there were no cans initially at R' and R'-1
- The cans to the left of L' now need to move 2 steps less, increasing profit by 2S_1
- The cans to the right of R' now need to move 2 steps more, decreasing profit by 2S_2
So, our overall profit increases by at least 2(S_1 - S_2), which is non-negative since S_1 \geq S_2. Note that it might increase by even more, since it could now be optimal for some more cans on the left to move, but this will never happen to cans on the right.
Since our profit doesn’t decrease, and the inequality S_1 \geq S_2 is maintained, we can keep moving left by two steps until we hit a position where there is a can at one of \{L'-1, L', L'+1, R'-1, R', R'+1\} (If we never stop, that means no cans are ever contained in this green area, i.e, the answer is 0, which is the lowest possible answer anyway).
Notice that this now gives us \mathcal{O}(N) candidates for the position L', instead of the around 10^9 we had earlier. If we are able to calculate the maximum profit for each L' quickly enough, taking the maximum over them will give us the value we are looking for.
Analyzing Cans
Let’s look at the cans instead of the positions now. Suppose the green zone is fixed at [L', R']. When does the i-th can contribute to the profit of this green zone?
- First off, if L' \leq X_i \leq R' then clearly no movement is required
- Otherwise, say X_i \lt L'. Then, the can needs to be moved d = L' - X_i steps, each costing B_i. This is only worth it when d\cdot B_i \leq A_i, i.e, d \leq \frac{A_i}{B_i}.
- A similar analysis can be done for the case when X_i \gt R'.
Let D = R - L. Frome the above, we see that a can at position X_i:
- Contributes A_i to all L' such that X_i - D \leq L' \leq X_i
- Contributes \max(0, A_i - d\cdot B_i) to X_i + d
- Contributes \max(0, A_i - d\cdot B_i) to X_i - D - d
Updates of this kind can be processed with the help of a sweepline.
Sweeping
If you do not know what a sweep line is, please go through this or this first. The idea there is for sweeping in 2D, but it carries over to 1D as well (really, in 1D it’s just a fancy name for iterating over a sorted array).
I’ll detail how to deal with the case when L' \gt X_i. The other two cases can be handled similarly.
The i-th can contributes A_i - (L' - X_i)\cdot B_i to a position X_i \leq L' \leq X_i + \frac{A_i}{B_i}. This can be split into two parts: A_i + X_i\cdot B_i and -L'\cdot B_i. Note that the first part depends only on i and is independent of L', while the second part is a product of L' with a single integer.
This allows us to do the following:
- For a can i with parameters (A_i, B_i, X_i), add the tuple (A_i + X_i\cdot B_i, -B_i) to position X_i, and the tuple (-A_i - X_i\cdot B_i, B_i) to position X_i + \left \lfloor \frac{A_i}{B_i} \right \rfloor + 1. The other two cases (X_i \lt R' and L' \leq X_i \leq R') can also be dealt with in this step, by adding appropriate tuples to the appropriate positions (exercise for the reader
)
Intuition
Adding the two tuples like this is essentially telling us to ‘turn on’ the i-th can at position X_i, and ‘turn it off’ at position X_i + \left \lfloor \frac{A_i}{B_i} \right \rfloor + 1 (which is where is stops giving us positive contribution). The first element of the tuple corresponds to the first part of the sum above, and the second part corresponds to the second. Note that combining two tuples is as simple as adding their corresponding coordinates, which means that when sweeping across positions, it’s enough to maintain the sum of the first and second coordinates respectively.
- Once this is done for all cans, iterate across all positions from left to right.
- Keep two variables P and Q, initially both zero.
- When processing a position x, consider all tuples that have been placed at x. Add their first element to P and the second element to Q. Note that, as described in the intuition section above, this tells us that at position x, all cans together would contribute P + x\dot Q to the green zone if it were to start at x.
- Now, if x is a good position (i.e, is one of the \mathcal{O}(N) candidates for L' that we computed earlier), compare P + x\cdot Q with the current answer and update it if needed.
Unfortunately, this is the kind of problem where describing the solution purely with words has the potential to make it somewhat confusing if you are seeing the idea for the first time. If you are unclear about the exact details, I encourage you to look at the attached code or others’ submissions.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per test.
CODE:
Setter
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;
using ii = pair<ll,ll>;
void solve(){
int n = readIntSp(1,3e5);
ll l = readIntSp(-1e9,1e9);
ll r = readIntLn(-1e9,1e9);
l*=2; //to do away with floating points
r*=2;
ll x[n], a[n], b[n];
rep(i,n){
if(i<n-1) x[i] = readIntSp(-1e9,1e9);
else x[i] = readIntLn(-1e9,1e9);
x[i]*=2; //to do away with floating points
}
rep(i,n){
if(i<n-1) a[i] = readIntSp(-1e9,1e9);
else a[i] = readIntLn(-1e9,1e9);
}
rep(i,n){
if(i<n-1) b[i] = readIntSp(-1e9,1e9);
else b[i] = readIntLn(-1e9,1e9);
}
vector<pair<ll,ii> > v;
ll p1,p2,p3,p4;
rep(i,n){
p2 = (l+x[i])/2;
p3 = (r+x[i])/2;
p1 = p2-a[i]/b[i];
p4 = p3+a[i]/b[i];
v.pb(mp(p1,mp(i,1)));
v.pb(mp(p2,mp(i,2)));
v.pb(mp(p3,mp(i,3)));
v.pb(mp(p4,mp(i,4)));
// as we need to check for integral k in op 2, we need to check
// for adjacent even coordinates in the new system (i.e. *2)
// so we will add dummy axes here
if(p1%2 != 0){
v.pb(mp(p1+1,mp(-1,-1)));
v.pb(mp(p1-1,mp(-1,-1)));
}
if(p2%2 != 0){
v.pb(mp(p2+1,mp(-1,-1)));
v.pb(mp(p2-1,mp(-1,-1)));
}
if(p3%2 != 0){
v.pb(mp(p3+1,mp(-1,-1)));
v.pb(mp(p3-1,mp(-1,-1)));
}
if(p4%2 != 0){
v.pb(mp(p4+1,mp(-1,-1)));
v.pb(mp(p4-1,mp(-1,-1)));
}
}
sort(v.begin(), v.end());
// for(auto h:v) cout<<h.ff<<" "<<h.ss.ff<<" "<<h.ss.ss<<endl;
// cout<<'\n';
ll var = 0, curr = 0;
ll ans = 0;
ll prv_cor = v[0].ff;
int i = 0;
int m = v.size();
while(i<m){ //iterate on the various possibilities of axes
curr += (v[i].ff-prv_cor)*var;
int j = i;
prv_cor = v[i].ff;
ll tmp = 0;
while(j<m && v[j].ff==v[i].ff){
if(v[j].ss.ss==1){
curr += a[v[j].ss.ff]%b[v[j].ss.ff];
var += b[v[j].ss.ff];
}
else if(v[j].ss.ss==2){
var -= b[v[j].ss.ff];
}
else if(v[j].ss.ss==3){
var -= b[v[j].ss.ff];
}
else if(v[j].ss.ss==4){
var += b[v[j].ss.ff];
tmp += a[v[j].ss.ff]%b[v[j].ss.ff];
}
j++;
}
if(v[i].ff%2 == 0) ans = max(ans, curr);
curr-=tmp;
i = j;
}
cout<<ans<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
t = readIntLn(1,1000);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
assert(sum_n<=3e5);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
// cerr<<"Maximum length : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll int
const ll INF_ADD=(2e9)+343;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=754974721;
const ll MAX=500500;
ll getp(ll p,ll l,ll r){
ll md=(p+l);
if((abs(md)%2)!=0){
return INF_ADD;
}
return md-r;
}
void solve(){
ll n,l,r; cin>>n>>l>>r;
vector<pair<ll,pair<ll,ll>>> track;
vector<ll> x(n+5),a(n+5),b(n+5);
for(ll i=1;i<=n;i++){
cin>>x[i];
}
for(ll i=1;i<=n;i++){
cin>>a[i];
}
for(ll i=1;i<=n;i++){
cin>>b[i];
}
for(ll i=1;i<=n;i++){
track.pb({x[i],{a[i],b[i]}});
track.pb({x[i]-1,{0,5}});
track.pb({x[i]+1,{0,5}});
ll rggt=x[i]+(a[i]+b[i]-1)/b[i];
track.pb({rggt-1,{0,5}});
ll lfft=x[i]-(a[i]+b[i]-1)/b[i];
rggt=lfft;
track.pb({rggt+1,{0,5}});
}
vector<pair<ll,pair<ll,ll>>> anot;
for(auto it:track){
ll s=getp(it.f,r,l);
ll t=getp(it.f,l,r);
if(s!=INF_ADD){
anot.pb({s,{0,5}});
}
if(t!=INF_ADD){
anot.pb({t,{0,5}});
}
}
for(auto it:anot){
track.pb(it);
}
sort(all(track));
n=track.size();
vector<long long> lft(n+5,0),rght(n+5,0),accum(n+5,0);
long long val=0,sub=0;
set<pair<ll,ll>> past;
unordered_map<ll,ll> leftmost,rightmost;
for(ll i=0;i<n;i++){
ll pos=i+1;
auto it=track[i];
accum[pos]=accum[pos-1]+it.s.f;
if(leftmost[it.f]==0){
leftmost[it.f]=pos;
}
while(!past.empty()){
auto j=*past.begin();
if(it.f>=j.f){
auto er=track[j.s];
val-=1LL*er.s.f+1LL*er.s.s*er.f;
sub-=er.s.s;
past.erase(j);
}
else{
break;
}
}
lft[pos]=val-sub*it.f;
if(it.s.f==0){
continue;
}
ll rat=(it.s.f+it.s.s-1)/it.s.s;
val+=1LL*it.s.f+1LL*it.s.s*it.f;
sub+=it.s.s;
past.insert({it.f+rat,i});
}
past.clear(); val=sub=0;
for(ll i=n-1;i>=0;i--){
ll pos=i+1;
auto it=track[i];
rightmost[it.f]=max(rightmost[it.f],pos);
while(!past.empty()){
auto j=*(--past.end());
if(it.f<=j.f){
auto er=track[j.s];
val-=1LL*er.s.f-1LL*er.s.s*er.f;
sub-=er.s.s;
past.erase(j);
}
else{
break;
}
}
rght[pos]=val+sub*it.f;
if(it.s.f==0){
continue;
}
ll rat=(it.s.f+it.s.s-1)/it.s.s;
val+=1LL*it.s.f-1LL*it.s.s*it.f;
sub+=it.s.s;
past.insert({it.f-rat,i});
}
long long ans=0;
for(auto it:track){
ll left_end=getp(it.f,r,l);
ll right_end=it.f;
if(right_end<left_end){
swap(left_end,right_end);
}
if(right_end==INF_ADD){
continue;
}
long long now=lft[leftmost[left_end]]+rght[rightmost[right_end]]+accum[rightmost[right_end]]-accum[leftmost[left_end]-1];
ans=max(ans,now);
}
cout<<ans<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}