(Sorted Distances) Problem Code: SORTDIS

editorial
1

The article cover the solution as per my understanding of the problem it is not the official solution so anyone is independent to discuss the solution of the problem given below:

#include <bits/stdc++.h>

using namespace std;

#define int long long int

void solve(){
	// write the code here
	int N, Q; cin >> N >> Q;

	vector<int> A(N);

		for (int &i: A) cin >> i;
	
	int X, Y, Z;

		while(Q--){
			cin >> X >> Y >> Z;

			// X value can only be 1 or 2 if its value is 1 then update the
            // range else apply the binary search over the given range
			if (X == 1){
				A[Y - 1] = Z;
			}else{
				int low = 0, high = 1e9 + 7;

					for (int i = Y; i < Z; i++){
						if (A[i] < A[i - 1])
							low = max(low, (A[i] + A[i - 1] + 1) / 2);
						else if (A[i] > A[i - 1])
							high = min(high, (A[i] + A[i - 1]) / 2);

						if (low > high) break;
					}

				cout << ((low > high) ? -1 : low) << endl;
			}		
		}
}

int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int test_case = 1;
    // std::cin >> test_case;
 
		for(int i = 1; i <= test_case; i++) { 
			solve();
		}
		
	return 0;
}
2

The runtime of this solution is \mathcal{O}(Q \times (R-L)) \equiv \mathcal{O}(QN) which is too slow and ideally shouldn’t pass. It passed only because test cases were weak.

The updates and queries are to be handled using 2 segment trees (one for lower bound and one for upper bound), this solution will have a runtime of \mathcal{O}(Q \log N)

3 Likes
3

SORTDIS Editorial … I think editorial is out now.