#include <bits/stdc++.h>
using namespace std;
# define int long long
# define fir first
# define sec second
# define pb push_back
const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;
void solve() {
int n, k, c, p; cin >> n >> k >> c >> p;
int in[n+5];
int out[n+5];
for(int i = 1; i<=n; i++) cin >> in[i];
for(int i = 1; i<=n; i++) cin >> out[i];
if(p == 1) {
int pref[n+5]; pref[0] = INT_MAX;
int suf[n+5]; suf[n+1] = INT_MAX;
for(int i = 1; i<=n; i++) pref[i] = min(pref[i-1], out[i]+c*(n-i-1));
for(int i = n; i>=1; i--) suf[i] = min(suf[i+1], out[i]+(i-1)*c);
// for(int i = 1; i<=n; i++) cerr << pref[i] << " "; cerr << endl;
// for(int i = 1; i<=n; i++) cerr << suf[i] << " "; cerr << endl;
for(int i = 1; i<=n; i++) {
int x = k-in[i];
int lo = i;
int hi = n;
int res = i-1;
int money = x+(i-1)*c;
while(lo <= hi) {
int mid = (lo+hi)/2;
if(suf[mid] <= money) lo = mid+1, res = mid;
else hi = mid-1;
}
int lo2 = 1;
int hi2 = i;
int res2 = i+1;
int money2 = x+(n-i-1)*c;
while(lo2 <= hi2) {
int mid = (lo2+hi2)/2;
if(pref[mid] <= money2) hi2 = mid-1, res2 = mid;
else lo2 = mid+1;
}
int lenl = i-res2+1;
int lenr = res-i+1;
int leftl = k-(in[i]+out[res2]+abs(i-res2)*c);
int leftr = k-(in[i]+out[res]+abs(i-res)*c);
// cerr << money << " " << money2 << endl;
// cerr << res2 << " " << res << " " << lenl << " " << lenr << " " << leftl << " " << leftr << endl;
// cerr << x << endl;
if((!lenl && !lenr) || x < 0) {
cout << "0 " << k << endl;
}
else if(lenl == lenr) cout << lenl << " " << max(leftl, leftr) << endl;
else if(lenl > lenr) cout << lenl << " " << leftl << endl;
else cout << lenr << " " << leftr << endl;
}
}
else {
for(int i = 1; i<=n; i++) {
int len = sqrt((double)(k-in[i])/c);
int l = max(1ll, i-len);
int r = min(n, len+i);
// cerr << i << " " << len << " " << l << " " << r << " " << endl;
int ansl = 0, ansr = 0;
int leftl = k, leftr = k;
int x = 1e3+1;
for(int j = l; x && j != i; x--, j++) {
int val = in[i]+out[j]+abs(i-j)*abs(i-j)*c;
if(val <= k) {
ansl = abs(i-j)+1;
leftl = k-val;
break;
}
}
x = 1e3+1;
for(int j = r; x && j != i; x--, j--) {
int val = in[i]+out[j]+abs(i-j)*abs(i-j)*c;
if(val <= k) {
ansr = abs(i-j)+1;
leftr = k-val;
break;
}
}
if(ansl == ansr) cout << ansl << " " << max(leftl, leftr) << endl;
else if(ansl > ansr) cout << ansl << " " << leftl << endl;
else cout<< ansr << " " << leftr << endl;
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
int t = 1;
if(mutipletestcase) cin >> t;
while(t--) solve();
}
// (j-i) <= len
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
