#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> val;
vector<long long> maxL, maxR;
vector<long long> dist;
vector<long long> D;
long long cost;
struct maxQueue{
deque<pair<long long, int> > d;
long long soma;
int ini, fim;
maxQueue(){
soma = 0;
ini = 0, fim = -1;
}
void push(long long val){
while(!d.empty() && d.back().first <= val - soma) d.pop_back();
d.push_back(make_pair(val - soma, ++fim));
}
void pop(){
if(!d.empty() && ini == d.front().second) d.pop_front();
ini++;
}
long long getMax(){
if(d.empty()) return 0;
return d.front().first + soma;
}
int add(long long val){
soma += val;
}
};
long long getLen(int id, int ini, int fim){
if(id > fim) id = ini;
if(id == ini) return cost;
return dist[id] - dist[id - 1];
}
long long test(int ini, int fim){
val[ini] = maxL[ini];
val[fim] = maxR[fim];
long long diam = 0;
long long sum = 0;
long long tam = dist[fim] - dist[ini] + cost;
int it = ini;
maxQueue fila;
fila.push(val[ini]);
for(int i = ini + 1; i < fim; i++){
fila.add(getLen(i, ini, fim));
sum += getLen(i, ini, fim);
val[i] = D[i];
fila.push(val[i]);
}
fila.add(getLen(fim, ini, fim));
sum += getLen(fim, ini, fim);
while(2 * sum > tam){
fila.pop();
it++;
if(it > fim) it = ini;
sum -= getLen(it, ini, fim);
}
diam = max(diam, val[fim] + fila.getMax());
fila.push(val[fim]);
for(int i = ini; i < fim; i++){
fila.add(getLen(i, ini, fim));
sum += getLen(i, ini, fim);
while(2 * sum > tam){
fila.pop();
it++;
if(it > fim) it = ini;
sum -= getLen(it, ini, fim);
}
diam = max(diam, val[i] + fila.getMax());
}
// maxQueue fila2;
// it = fim;
// sum = 0;
// fila2.push(val[fim]);
// for(int i = fim - 1; i > ini; i--){
// fila2.add(getLen(i + 1, ini, fim));
// sum += getLen(i + 1, ini, fim);
// fila2.push(val[i]);
// }
// fila.add(getLen(ini + 1, ini, fim));
// sum += getLen(ini + 1, ini, fim);
// while(2 * sum > tam){
// fila2.pop();
// it--;
// if(it < ini) it = fim;
// sum -= getLen(it + 1, ini, fim);
// }
// printf("Right: %d = %lld (%lld) (%d)\n", ini, val[ini] + fila2.getMax(), sum, it);
// if(sum != 0)
// diam = max(diam, val[ini] + fila2.getMax());
// fila2.push(val[ini]);
// for(int i = fim; i > ini; i--){
// fila2.add(getLen(i + 1, ini, fim));
// sum += getLen(i + 1, ini, fim);
// while(2 * sum > tam){
// fila2.pop();
// it--;
// if(it < ini) it = fim;
// sum -= getLen(it + 1, ini, fim);
// }
// printf("Right: %d = %lld (%lld) (%d)\n", i, val[i] + fila2.getMax(), sum, it);
// if(sum != 0)
// diam = max(diam, val[i] + fila2.getMax());
// }
return diam;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
cost = c;
dist = vector<long long> (n);
val = vector<long long> (n);
maxL = vector<long long> (n);
maxR = vector<long long> (n);
D = vector<long long> (n);
dist[0] = 0;
long long len = 0;
maxL[0] = d[0];
D[0] = d[0];
for(int i = 1; i < n; i++){
dist[i] = dist[i - 1] + l[i - 1];
maxL[i] = max((long long)d[i], maxL[i - 1] + l[i - 1]);
D[i] = d[i];
}
maxR[n - 1] = d[n - 1];
for(int i = n - 2; i >= 0; i--){
maxR[i] = max((long long)d[i], maxR[i + 1] + l[i]);
}
len = dist[n - 1];
long long maxi = 0;
int ini = 0;
for(int i = 0; i < n; i++)
if(d[i] + dist[i] > maxi) maxi = d[i] + dist[i], ini = i;
maxi = 0;
int fim = 0;
for(int i = 0; i < ini; i++)
if(dist[ini] - dist[i] + d[ini] + d[i] > maxi) maxi = dist[ini] - dist[i] + d[ini] + d[i], fim = i;
for(int i = ini + 1; i < n; i++)
if(dist[i] - dist[ini] + d[ini] + d[i] > maxi) maxi = dist[i] - dist[ini] + d[ini] + d[i], fim = i;
if(ini > fim) swap(ini, fim);
long long ans = maxi;
int j = ini + 1;
for(int i = ini; i < fim; i++){
j = max(j, i + 1);
while(1){
long long aux = test(i, j);
ans = min(ans, aux);
if(j == fim || aux > maxL[i] + maxR[j] + cost) break;
j++;
}
}
return ans;
}
Compilation message
shortcut.cpp: In member function 'int maxQueue::add(long long int)':
shortcut.cpp:34:2: warning: no return statement in function returning non-void [-Wreturn-type]
34 | }
| ^
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:131:12: warning: variable 'len' set but not used [-Wunused-but-set-variable]
131 | long long len = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
