#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 10000000000000000LL
int n, c;
vector<long long> x, d;
int sp[1000005][20];
int lg[1000005];
int get(int l, int r){
int sz = lg[r - l + 1];
int q2 = sp[r][sz];
int q1 = sp[l + (1 << sz) - 1][sz];
if(x[q1] - d[q1] < x[q2] - d[q2]) return q1;
return q2;
}
bool pos(long long len){
long long bpmx, bpmn, bmmx, bmmn, pmx, pmn, mmx, mmn;
bpmx = bmmx = mmn = pmn = inf;
bpmn = bmmn = mmx = pmx = -inf;
int mid = 0;
int itm = 0, itp = 0, t = 0, r;
for(itp = 1; itp < n; itp++){
if(x[itp] + d[itp] - x[mid] + d[mid] > len){
t = max(mid, t);
if(t != itp - 1){
r = get(t + 1, itp - 1);
while(x[itp] + d[itp] - x[r] + d[r] > len){
t = r;
if(t == itp - 1) break;
r = get(t + 1, itp - 1);
}
}
while(itm <= t){
mmx = max(mmx, x[itm] - d[itm]);
mmn = min(mmx, x[itm] - d[itm]);
pmx = max(pmx, x[itm] + d[itm]);
pmn = min(pmn, x[itm] + d[itm]);
itm++;
}
}
if(itm){
bpmx = min(bpmx, len - c + mmn + x[itp] - d[itp]);
bpmn = max(bpmn, c - len + pmx + x[itp] + d[itp]);
bmmx = min(bmmx, len - c - pmn + x[itp] - d[itp]);
bmmn = max(bmmn, c - len - mmx + x[itp] + d[itp]);
}
if(x[itp] - d[itp] <= x[mid] - d[mid]) mid = itp;
}
if(bmmx < bmmn || bpmx < bpmn) return 0;
int i, imn = 0, imx = 0;
for(i = 0; i < n; i++){
while(x[i] - x[imx] > bmmx) imx++;
while(x[i] - x[imn] >= bmmn) imn++;
if(imn > imx){
if(x[i] + x[imn - 1] <= bpmx && x[i] + x[imn - 1] >= bpmx) return 1;
if(x[i] + x[imx] <= bpmx && x[i] + x[imx] >= bpmx) return 1;
}
}
imn = n - 1;
imx = n - 1;
for(i = 0; i < n; i++){
while(imx >= 0 && x[i] + x[imx] > bpmx) imx--;
while(imn >= 0 && x[i] + x[imn] >= bpmn) imn--;
if(i > imx) return 0;
if(imn < imx){
if(x[imx] - x[i] <= bmmx && x[imx] - x[i] >= bmmn) return 1;
if(x[imn + 1] - x[i] <= bmmx && x[imn + 1] - x[i] >= bmmn) return 1;
}
}
return 0;
}
long long find_shortcut(int n, vector<int> le, vector<int> d, int c){
long long m, l = 0, r = 100000;
::c = c;
::n = n;
for(auto& t : d){
::d.push_back(t);
}
x.push_back(0);
for(auto& t : le)
x.push_back(x.back() + t);
for(int i = 0; i < n; i++){
sp[i][0] = i;
for(int j = 1; j < 20; j++){
if((1 << j) > i) break;
int q1, q2;
q1 = sp[i][j - 1];
q2 = sp[i - (1 << (j - 1))][j - 1];
if(x[q1] - d[q1] < x[q2] - d[q2])
sp[i][j] = q1;
else sp[i][j] = q2;
}
}
for(int i = 2; i < n; i++){
lg[i] = lg[i >> 1] + 1;
}
while(l != r){
m = (l + r) >> 1;
if(pos(m)) r = m;
else l = m + 1;
}
return l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
