Minimum Prefix Difference
National Olympiad — Regional round
Submission name: mindiff.cpp
Problem summary
For each requested prefix length M, find the minimum absolute difference between two distinct positions among a₁…a_M.
Input
N Q, N values, then Q prefix lengths.
Output
Q answers in query order on one line.
Constraints
2 ≤ N ≤ 100,000; 1 ≤ Q ≤ 100,000; 0 ≤ aᵢ ≤ 10⁹; 2 ≤ M ≤ N.
Worked example
An independently prepared example for this explanation.
Input
4 3 9 1 6 6 2 3 4
Output
8 3 0
Solution analysis
- Insert values in an ordered set while scanning the array.
- Only the new value’s predecessor and successor can improve the previous minimum. Record the result for each prefix, then answer by lookup.
Why it works
All old pairs retain their differences. Among pairs using the new value, the nearest values in sorted order minimize absolute difference. A duplicate produces zero.
Complexity: O(N log N+Q) time, O(N) space.
Watch out. Equal values at different positions form a valid pair of difference zero.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: All old pairs retain their differences. Among pairs using the new value, the nearest
// values in sorted order minimize absolute difference.
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<tuple>
#include<climits>
#include<iterator>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
set<long long>s;
vector<long long>ans(n+1);
long long best=LLONG_MAX;
for(int i=1;i<=n;i++){
long long x;
cin>>x;
auto it=s.lower_bound(x);
if(it!=s.end()){
best=min(best,*it-x);
}
if(it!=s.begin()){
best=min(best,x-*prev(it));
}
s.insert(x);
ans[i]=best;
}
for(int i=0;i<q;i++){
int m;
cin>>m;
cout<<ans[m]<<(i+1==q?'\n':' ');
}
}