Temporary Road Sign Changes
Autumn Tournament (2024)
Submission name: signs.cpp
Problem summary
Speed-limit signs push a limit onto a stack; a cancellation sign pops the current limit and restores the previous one. The initial limit is120. Each independent query changes one sign. Find the fastest legal journey time for every query.
Source clarification. The source provides no separate global Q bound; the full-constraint subtask table uses Q≤100000. This solution follows the official offline shifted-stack method. Editorial: https://infos.infosbg.com/files/Contests/ETI/2024/C/analyses/C2_signs_analysis.pdf
Input
N L; N pairs distance speed (speed−1 means cancellation); Q; Q pairs signIndex newSpeed.
Output
For each independent query, the journey time in hours, with absolute error below0.001.
Constraints
1 ≤ N≤100000; N+1≤L≤10^9; strictly increasing interior sign distances; limits10..119 or−1. The subtask table allows Q≤100000. No original or queried journey pops the initial120 limit.
Worked example
Original statement sample, displayed with additional decimal precision.
Input
7 2070 120 10 170 20 270 30 420 -1 620 50 870 -1 1170 100 11 1 25 2 25 3 25 4 25 5 25 6 25 7 25 2 -1 3 -1 5 -1 7 -1
Output
52.0000000000 49.0000000000 56.0000000000 50.0000000000 60.0000000000 52.0000000000 82.0000000000 30.0000000000 44.1666666667 62.5000000000 136.0000000000
Solution analysis
- First simulate the original stack and total, recording the total road length controlled by every opening sign. Group queries by their changed position. A second left-to-right pass consumes each traversed segment, so remaining[id] always means that sign’s still-untraveled original active distance. Future signs not currently in the stack behave identically under a query and need no adjustment.
- For the current open stack v0,...,vr, maintain three weighted totals: normal=Σ remaining[vi]/speed[vi]; up=Σ remaining[vi]/speed[vi+2] where i+2 exists; down=Σ remaining[vi]/speed[vi−2] where i≥2. Pushes, pops and consuming the top sign’s distance change only a constant number of these terms. This is why the queries are grouped offline rather than independently resimulated.
- Changing an opening sign to another opening only changes its own remaining contribution. Changing an opening to a cancellation removes two stack levels relative to the original path, so replace normal by down. Changing a cancellation to an opening adds two levels: use up for lower entries and handle the top two explicitly, using the popped sign and the new speed. Query validity guarantees no forbidden below-default levels are used.
- In the first source query, sign1 changes from10 to25. Its originally active50 kilometers now take2 hours instead of5. The original55-hour journey therefore becomes52 hours. Other sign types can affect many disjoint road segments; the shifted totals aggregate all of them.
Why it works
The first simulation gives the exact original contribution of every road segment. In the second pass, the maintained totals follow their definitions by local push/pop/subtraction updates. Relative to an unchanged prefix, replacing push by pop shifts surviving original stack levels by−2, while replacing pop by push shifts them by+2. Future pushes temporarily hide the stack but do not change this correspondence. Therefore replacing the affected normal total by the appropriate shifted total changes exactly the altered segments and leaves all others untouched.
Watch out. Queries are independent. The query position is a sign index, not a kilometer. Cancellations restore the immediately preceding active limit, not always120. Use long double internally and enough output precision. The source omits a separate global Q bound; its full subtask table gives Q≤100000.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iomanip>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long length;
cin>>n>>length;
vector<long long>distance(n+2,0),remaining(n+1,0);
vector<int>speed(n+1,120);
for(int i=1;i<=n;i++){
cin>>distance[i]>>speed[i];
}
distance[n+1]=length;
vector<int>stack(1,0);
long double original=0;
for(int i=0;i<=n;i++){
if(i>0){
if(speed[i]==-1){
stack.pop_back();
}
else{
stack.push_back(i);
}
}
long long segment=distance[i+1]-distance[i];
remaining[stack.back()]+=segment;
original+=static_cast<long double>(segment)/speed[stack.back()];
}
int q;
cin>>q;
vector<vector<pair<int,int>>>queries(n+1);
for(int i=0;i<q;i++){
int position,replacement;
cin>>position>>replacement;
queries[position].push_back({replacement,i});
}
vector<long double>answers(q);
stack.assign(1,0);
long double normal=static_cast<long double>(remaining[0])/speed[0];
long double up=0;
long double down=0;
for(int i=1;i<=n;i++){
// Consume the segment before this sign under the original active limit.
long long segment=distance[i]-distance[i-1];
int oldSize=static_cast<int>(stack.size());
int active=stack.back();
remaining[active]-=segment;
normal-=static_cast<long double>(segment)/speed[active];
if(oldSize>=3){
down-=static_cast<long double>(segment)/speed[stack[oldSize-3]];
}
int popped=-1;
if(speed[i]==-1){
popped=stack.back();
normal-=static_cast<long double>(remaining[popped])/speed[popped];
if(oldSize>=3){
down-=static_cast<long double>(remaining[popped])/speed[stack[oldSize-3]];
up-=static_cast<long double>(remaining[stack[oldSize-3]])/speed[popped];
}
stack.pop_back();
}
else{
if(oldSize>=2){
up+=static_cast<long double>(remaining[stack[oldSize-2]])/speed[i];
down+=static_cast<long double>(remaining[i])/speed[stack[oldSize-2]];
}
normal+=static_cast<long double>(remaining[i])/speed[i];
stack.push_back(i);
}
for(auto[replacement,index]:queries[i]){
if(speed[i]!=-1&&replacement!=-1){
answers[index]=original+
static_cast<long double>(remaining[i])*(1.0L/replacement-1.0L/speed[i]);
}
else if(speed[i]!=-1){
answers[index]=original+down-normal;
}
else if(replacement==-1){
answers[index]=original;
}
else{
int size=static_cast<int>(stack.size());
long double changed=up+static_cast<long double>(remaining[stack.back()])/replacement;
if(size>=2){
changed+=static_cast<long double>(remaining[stack[size-2]])/speed[popped];
}
answers[index]=original+changed-normal;
}
}
}
cout<<fixed<<setprecision(10);
for(long double answer:answers){
cout<<answer<<'\n';
}
}