Untitled
unknown
c_cpp
10 months ago
1.6 kB
6
Indexable
#include <bits/stdc++.h> using namespace std; int partition( vector<int> &arr, int p, int r ) { random_shuffle( arr.begin() + p, arr.begin() + r + 1 ); int i = p; for ( int j = p; j < r; j++ ) { if ( arr[j] <= arr[r] ) { swap( arr[j], arr[i] ); i++; } } swap( arr[i], arr[r] ); return i; } void quicksort( vector<int> &arr, int p, int r ) { if ( p < r ) { int q = partition( arr, p, r ); quicksort( arr, p, q - 1 ); quicksort( arr, q + 1, r ); } } int binary_search(vector<int> &arr, int n, int val) { int l = 0, r = n - 1, mid; while (l <= r) { mid = (l + r) / 2; if(arr[mid] == val) return mid; else if(arr[mid] > val) r = mid - 1; else l = mid + 1; } return mid; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, q; cin >> n >> q; vector<int> arr( n ); for ( auto &x : arr ) cin >> x; quicksort( arr, 0, n - 1 ); for ( int i = 0; i < q; i++ ) { int l, r; cin >> l >> r; cout << l << " " << r << "\n"; if ( l > arr[n - 1] ) cout << "0" << "\n"; else { int num = 0; int li = binary_search( arr, n, l ); int ri = binary_search( arr, n, r ); for ( int i = li; i <= ri; i++ ) { if ( arr[i] >= l && arr[i] <= r ) { num++; } } cout << num << "\n"; } } }
Editor is loading...
Leave a Comment