Educational Codeforces Round 161 (Rated for Div. 2) 1922C - Closest Cities

  Problem Link : https://codeforces.com/contest/1922/problem/C

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. int32_t main() {
5. ios_base::sync_with_stdio(0);
6. cin.tie(0);
7. int t;
8. cin >> t;
9. while (t--) {
10. int n;
11. cin >> n;
12. vector < int > a(n);
13. for (int i = 0; i < n; i++) {
14. cin >> a[i];
15. }
16. vector < int > forward(n), backward(n);
17. forward[0] = 0;
18. forward[1] = 1;
19. for (int i = 2; i < n; i++) {
20. if (a[i] - a[i - 1] < a[i - 1] - a[i - 2]) {
21. forward[i] = forward[i - 1] + 1;
22. } else {
23. forward[i] = forward[i - 1] + a[i] - a[i - 1];
24. }
25. }
26. backward[n - 1] = 0;
27. backward[n - 2] = 1;
28. for (int i = n - 3; i >= 0; i--) {
29. if (a[i + 2] - a[i + 1] > a[i + 1] - a[i]) {
30. backward[i] = backward[i + 1] + 1;
31. } else {
32. backward[i] = backward[i + 1] + a[i + 1] - a[i];
33. }
34. }
35. int q;
36. cin >> q;
37. while (q--) {
38. int x, y;
39. cin >> x >> y;
40. x--, y--;
41. if (x < y) cout << forward[y] - forward[x] << '\n';
42. else cout << backward[y] - backward[x] << '\n';
43. }
44. }
45. return 0;
46. }