Nearest Equal Values on Both Sides
National Olympiad — Regional round (2023 season)
Submission name: red.cpp
Problem summary
For each query K, report the nearest equal value strictly left and right of position K; use zero when missing.
Input
N values, then T and T query positions.
Output
Left and right positions for each query.
Constraints
1≤N,T≤100000;1≤a[i]<100000; positions1-based.
Worked example
Input and output for the worked example discussed below.
Input
8 2 4 5 4 4 2 7 4 3 1 8 4
Output
0 6 5 0 2 5
Solution analysis
- Scan forwards with last[v] storing the most recent index of v. Read that index into previous[i] before setting last[v]=i.
- Clear the table and scan backwards to obtain next[i] using the same invariant. Each query then takes two array lookups.
- Value4 occurs at2,4,5,8. Query4 returns2,5, whereas query8 returns5,0. Updating after reading prevents returning K itself.
Why it works
Before each forward step last[v] is exactly the largest earlier index with value v; the reverse scan analogously finds the smallest later index.
Complexity: O(N+T+V) time and O(N+V) space, V=100000; O(1) per query.
Watch out. Use zero for absence and exclude the queried occurrence itself. Read all values before T.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// Before each forward step last[v] is exactly the largest earlier index with value v; the reverse scan
// analogously finds the smallest later index.
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>a(n+1),previous(n+1),next(n+1),last(100000,0);
for(int i=1;i<=n;i++){
cin>>a[i];
previous[i]=last[a[i]];
last[a[i]]=i;
}
fill(last.begin(),last.end(),0);
for(int i=n;i>=1;i--){
next[i]=last[a[i]];
last[a[i]]=i;
}
int q;
cin>>q;
while(q--){
int p;
cin>>p;
cout<<previous[p]<<' '<<next[p]<<'\n';
}
}