Untitled
unknown
plain_text
a year ago
1.7 kB
5
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define endl "\n" const double PI = 3.14159265358979; const ll INF = 1e18 + 7; const ll MOD = 1e9 + 7; const ll nax = 1000005; const int LOG = 25; int findIn(vector<int> &a, int left, int right, int key, bool asc) { int ans = -1; while(left <= right) { int mid = (left + right) / 2; if (a[mid] == key) { return mid; } else if (a[mid] > key) { if (asc) { right = mid - 1; } else { left = mid + 1; } } else { if (asc) { left = mid + 1; } else { right = mid - 1; } } } return ans; } void solve() { int n, q, k; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int peak = n - 1, left = 0, right = n - 2; while(left <= right) { int mid = (left + right) / 2; if (a[mid] > a[mid + 1]) { peak = mid; right = mid - 1; } else { left = mid + 1; } } while(q--) { cin >> k; int x1 = findIn(a, 0, peak, k, true); int x2 = findIn(a, peak + 1, n - 1, k, false); if (x1 > x2) { swap(x1, x2); } if (x1 != -1) { cout << x1 + 1 << " "; } if (x2 != -1) { cout << x2 + 1; } cout << endl; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin >> t; while(t--) solve(); return 0; }
Editor is loading...
Leave a Comment