706B - Interesting drink - CodeForces Solution


binary search dp implementation *1100

Please click on ads to support us..

Python Code:

from bisect import bisect_right


n_arr = int(input())
arr = list(map(int, input().split(' ')))

arr.sort()
n = int(input())
for i in range(n):
    coins = int(input())
    print(bisect_right(arr, coins))

C++ Code:

//#define _GLIBCXX_DEBUG 1
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define int               long long
#define lwr               lower_bound
#define upr               upper_bound
#define pb                push_back
#define ff                first
#define ss                second
#define nl                "\n"
#define go(x)			  {cout<<x<<nl; return;}
#define all(x)            x.begin(),x.end()
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define oset               tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>


const long long INF=1e18;
const long long mod=1e9+7;
const int nax=4e5+10;

int get_bit_count(int n){
	return __builtin_popcountll(n);
}

int binpow(int a,int b,int m){
    int res=1;
    while(b>0){
        if(b&1)
        {
		 	res=(res*(a%m))%m;
		 	b--;
        }
		else
		{
			a=((a%m)*(a%m))%m;
			b/=2;
		}
    }
    return res;
}

int mod_inv(int n, int p)
{
    return binpow(n, p - 2, p);
}

int gcd(int a,int b){
	if(b==0){return a;}
	return gcd(b,a%b);
}

vector<int> find_lps(string s){
	int n=s.size();
	vector<int> arr(n,0);
	for(int i=1;i<n;i++){
		int j=arr[i-1];
		while(j>0 && s[j]!=s[i]){
			j=arr[j-1];
		}
		if(s[j]==s[i]){
			j++;
		}
		arr[i]=j;
	}
	return arr;
}

class segtree
{
    public:
    	int size;
    	int n;
    	vector<int> seg;
    	void init(int k)
    	{
    		n=k;
    		size=1;
    		while(size<n) size*=2;
    		seg=vector<int>(2*size);
		}

		void merge(int & seg, int& left,int& right)
		{
			seg=left+right;
		}
		void build(int x, int lx,int rx,vector<int>& arr)
		{
			if(rx==lx+1)
			{
				if(lx<n) seg[x]=arr[lx];
				return;
			}
			int m=(lx+rx)/2;
			build(2*x+1,lx,m,arr);
			build(2*x+2,m,rx,arr);
			merge(seg[x],seg[2*x+1],seg[2*x+2]);
		}

		void build(vector<int>& arr){build(0,0,size,arr);}

		void set(int i, int v, int x, int lx, int rx)
		{
			if(rx==lx+1)
			{
				if(lx<n) seg[x]=v;
				return;
			}
			int m=(lx+rx)/2;
			if(i<m) set(i,v,2*x+1,lx,m);
			else set(i,v,2*x+2,m,rx);
			merge(seg[x],seg[2*x+1],seg[2*x+2]);
		}

		void set(int i, int v){set(i,v,0,0,size);}

		int find(int x, int lx, int rx, int l,int r)
		{
			if(rx<=l or lx>=r) return 0;
			if(lx>=l and rx<=r) return seg[x];
			int m=(lx+rx)/2;
			return find(2*x+1,lx,m,l,r)+find(2*x+2,m,rx,l,r);
		}

		int find(int l,int r){return find(0,0,size,l,r);}

};

bool isPrime(int n){
	if(n == 1) return false;
	for(int i = 2 ; i * i <= n ; i++){
		if(n % i == 0) return false;
	}

	return true;
}

int getFact(int n){
	int ans = INT_MAX;

	for(int i = 2 ; i * i <= n ; i++){
		if(n % i == 0){
			ans = min(ans , i);
			ans = min(n/i , ans);
		}
	}

	return ans;
}

	// int n;
	// cin>>n;

	// vector<int> v;

	// for(int i = 0 ; i< n ; i++){
	// 	int temp;
	// 	cin>>temp;
	// 	v.push_back(temp);
	// }

// You Got This.....

void testcase(int test)
{
	int n;
	cin>>n;

	vector<int> v;
	for(int i = 0; i< n ; i++){
		int temp;
		cin>>temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());

	int q;
	cin>>q;
	while(q--){
		int p;
		cin>>p;

		int l = -1;
		int r = n;

		while(r > l + 1){
			int m = (l + r)/2;
			if(v[m]<= p){
				l = m;
			}else{
				r = m;
			}
		}

		cout<<l + 1<<"\n";
	}
}


signed main(){
	IOS;
	int t=1;
	// cin>>t;

	for(int i=1;i<=t;i++)
	{
		testcase(i);
	}
	return 0;
}


Comments

Submit
0 Comments
More Questions

1566B - MIN-MEX Cut
678C - Joty and Chocolate
1352E - Special Elements
1520E - Arranging The Sheep
1157E - Minimum Array
1661D - Progressions Covering
262A - Roma and Lucky Numbers
1634B - Fortune Telling
1358A - Park Lighting
253C - Text Editor
365B - The Fibonacci Segment
75A - Life Without Zeros
1519A - Red and Blue Beans
466A - Cheap Travel
659E - New Reform
1385B - Restore the Permutation by Merger
706A - Beru-taxi
686A - Free Ice Cream
1358D - The Best Vacation
1620B - Triangles on a Rectangle
999C - Alphabetic Removals
1634C - OKEA
1368C - Even Picture
1505F - Math
1473A - Replacing Elements
959A - Mahmoud and Ehab and the even-odd game
78B - Easter Eggs
1455B - Jumps
1225C - p-binary
1525D - Armchairs