https://oj.luyencode.net/problem/SEARCH3?fbclid=IwAR2kV070cALbS80odhpv6EGxsH2ncReiwNW2qR9uqAWJlY7inju4jAeYkx8

Mình đã viết một lời giải cho bài này với độ phức tạp là $O(\max(M,N) \times \logN$, tuy nhiên 2 testcase sau mình bị TLE (thời gian chạy rơi vào khoảng 19xx ms). Mọi người có thể giúp mình chỉ ra chỗ chưa tối ưu được không.

Xem code

#include using namespace std; #define int long long #define REP(i, a, b) for(int i = a; i <= b; ++i) #define REPD(i, b, a) for(int i = b; i >= a; --i) #define sz(s) (int)(s).size() #define pii pair #define vi vector #define vii vector int bs(vii a, int left, int right, int value) { int ans = 0; while(left <= right) { int mid = (left + right) / 2; if(a[mid].first == value) { ans = mid; right = mid - 1; } else if(value < a[mid].first) { right = mid - 1; } else { left = mid + 1; } } return ans; } void solve() { int n, m; cin >> n >> m; vii a(n + 1); vi b(m); REP(i, 1, n) { cin >> a[i].first; a[i].second = i; } REP(i, 0, m - 1) cin >> b[i]; sort(a.begin() + 1, a.end()); REP(i, 0, m - 1) { int key = bs(a, 1, n, b[i]); if(key == 0) cout << 0 << " "; else cout << a[key].second << " "; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int numTest = 1; // cin >> numTest; while(numTest--) { solve(); } }

luyencode / comments

https://oj.luyencode.net/problem/SEARCH3?fbclid=IwAR2kV070cALbS80odhpv6EGxsH2ncReiwNW2qR9uqAWJlY7inju4jAeYkx8 #917

Chi tiết bài tập - Luyện Code Online