cautare binara`

----------------- PB 3163-----------------
#include <fstream>

using namespace std;

ifstream f("secvmaxval.in");
ofstream g("secvmaxval.out");

int cautare(long long v[], int n, int i, long long x)
{
    int s=i, d=n, m;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]-v[i-1]>x) d=m-1;
        else s=m+1;
    }
    return d;
}
int main()
{
    int n, i, j, maxx=0;
    long long v[200001], val;
    f>>n>>val;
    v[0]=0;
    for(i=1; i<=n; i++)
    {
        f>>v[i];
        v[i]=v[i]+v[i-1];
    }
    for(i=1; i<=n; i++)
    {
        j=cautare(v, n, i, val);
        if(j-i+1>maxx) maxx=j-i+1;
    }
    g<<maxx;
}
----------------- PB 2455-----------------

#include <bits/stdc++.h>
using namespace std;
ifstream f("plaja2.in");
ofstream g("plaja2.out");
struct zile{
    long long nr,res;
}x[100005];
int main()
{
    long long n,k,dif,i,maxx=0,a,b,z;
    f>>n>>k>>dif;
    for(i=1;i<=k;i++)
        f>>x[i].nr>>x[i].res;
    if(maxx<x[1].res+dif*x[i].nr-dif)
        maxx=x[1].res+dif*x[i].nr-dif;
    if(maxx<x[k].res+(n-x[k].nr)*dif)
        maxx=x[k].res+(n-x[k].nr)*dif;
    for(i=1;i<k;i++){
        z=x[i+1].nr-x[i].nr-1;
        a=x[i].res;
        b=x[i+1].res;
        if(a>b) swap(a,b);
        while(z){
            z--;
            if(a<=b)
                a+=dif;
            else
                b+=dif;
        }
        if(maxx<max(a,b))
            maxx=max(a,b);
    }
    g<<maxx;
    return 0;
}

----------------- PB 2454-----------------

#include <bits/stdc++.h>
using namespace std;
ifstream f("bsrec.in");
ofstream g("bsrec.out");
int minn[1005],maxx[1005],sol[1005];
int main()
{
    int T,Q,n,IT,val,left,right,l,r,i;
    f>>T;
    for(int t=1;t<=T;t++){
        f>>n>>Q;
        memset(minn,0,1001);
        for(i=1;i<=1000;i++){
            maxx[i]=1000000001;
            minn[i]=0;
            sol[i]=0;
        }

        for(int q=1;q<=Q;q++){
            f>>val>>IT;
            f>>left>>right;
            for(int it=2;it<=IT;it++){
                f>>l>>r;
                if(l==left)
                    if(minn[(left+right)/2]<val)
                        minn[(left+right)/2]=val;
                if(r==right)
                    if(maxx[(left+right)/2]>=val)
                        maxx[(left+right)/2]=val-1;
                left=l; right=r;
            }
        }
//        for(i=1;i<=n;i++)
//            g<<minn[i]<<" ";
//        g<<"\n";
//        for(i=1;i<=n;i++)
//            g<<maxx[i]<<" ";
//        g<<"\n\n";
        for(i=1;i<=n;i++){
            sol[i]=max(sol[i-1]+1,minn[i]);
            if(maxx[i]<sol[i]){
                g<<"-1";
                break;
            }
        }
        if(i==n+1)
            for(i=1;i<=n;i++)
                g<<sol[i]<<" ";


        g<<"\n";

    }
    return 0;
}

----------------- PB 2453-----------------

#include <fstream>
#include <iostream>

using namespace std;
int n,m,c[1001],fv[1000000];

int main()
{
    ifstream f("rosii_mici.in");
    ofstream g ("rosii_mici.out");
    int i,j,Q,x,maxx,a[1001],maxim=0,k;
    f>>n>>m>>Q;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            f>>x;
            k=j-1;
            while(k>0 and c[k]>x)
            {
                 c[k+1]=c[k];
                 k--;
            }
            c[k+1]=x;
        }
            for(j=1;j<=m;j++)
            {
                if(fv[c[j]]<i*j)
                    maxim=i*j;
                else maxim=fv[c[j]];
                    fv[c[j]]=maxim;
            }
    }
    for(i=1;i<=1000000;i++)
    {
         if(fv[i]<fv[i-1])
            maxim=fv[i-1];
        else
            maxim=fv[i];
        fv[i]=maxim;
    }

    for(i=1;i<=Q;i++)
    {
        f>>x;
        g<<fv[x]<<"\n";
    }

    return 0;
}

----------------- PB 2252-----------------

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("profu.in");
ofstream fout("profu.out");
int n, k, i, maxx=0;
int v[500001];
int verif(long long  X)
{
    int r=0, i, nr=0;
    for(i=1; i<=n; i++)
    {
        r=r+v[i];
        if(r>X)
        {
            nr++;
            r=v[i];
        }
    }
    nr++;
    if(nr<=k)   return 1;
    else  return 0;
}
int main()
{
    fin >> n >> k;
    for(i=1; i<=n; i++)
    {
        fin >> v[i];
        if(v[i]>maxx)   maxx=v[i];
    }
    long long st, dr, mij, SOLUTIE;
    st=maxx;
    dr=500000000000;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(verif(mij))
        {
            SOLUTIE=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    fout << SOLUTIE;
    return 0;
}

----------------- PB 2621-----------------

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("spower2.in");
ofstream fout("spower2.out");
long long p[35], v[1001];
int main()
{
    long long aux=1;
    long long n, i, st, dr, mij, nr=0, a, numar, j, ok;
    //generez toate puterile lui 2 pana la 2^31
    while(nr<=31)
    {
        nr++;
        p[nr]=aux;
        if(nr<=31) aux=aux*2;
    }
    //memorez toate combinatiile posibile de doua puteri ale lui 2
    nr=0;
    for(i=1; i<=31; i++)
        for(j=i+1; j<=31; j++)
        {
            nr++;
            v[nr]=p[i]+p[j];
        }
    fin >> n;
    sort(v+1, v+nr+1);
    for(i=1; i<=n; i++)
        {
            fin >> a;
        //caut binar cel mai apropiat numar >= a in vectorul v
        //daca am gasit pe a in vectorul v, vom afisa v[mij], altfel
        //vom avea cazul st>dr si vom afisa v[st]
            st=1;
            dr=nr;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(a==v[mij])   dr=-2;
                else
                    if(a>v[mij])   st=mij+1;
                else
                    if(a<v[mij])   dr=mij-1;
            }
            if(dr==-2)   st=mij;
            fout << v[st] << " ";
        }
    return 0;
}

----------------- PB 536-----------------

#include <bits/stdc++.h>

using namespace std;

int v[1001],simulare[1001];
int s;
int n,m;

int suma(int x)
{
    s=0;
    for(int i=1;i<=n;i++)
        s+=(x/v[i]);
    return s;
}

int cautbin(int st, int dr)
{
    int mij;
   // mij=(st+dr)/2;
    ///int sum=suma(mij);
    int sum;
    //sum/=2;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        sum=suma(mij);
        if(sum<m)
            st=mij+1;
        else if(sum>m)
                dr=mij-1;
        else if(sum==m)
                return mij;
    }
    return st;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    int i=1;
    int poz=cautbin(1,m);
    /*while(s<m)
    {
        for(int j=1;j<=n;j++)
            if(i%v[j]==0)
                s++;
        i++;
    }

    cout<<i-1;*/
    cout<<poz;
    return 0;
}

----------------- PB 1594-----------------

#include <bits/stdc++.h>

using namespace std;

ifstream f("maraton.in");
ofstream g("maraton.out");

int v[100001];

int binsearch(int x,int st, int dr)
{
    int m;

    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]>x)
            dr=m-1;
        else
            st=m+1;
    }
    return dr;
}

int main()
{
    int n,x,y;
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>x>>y;
        v[i]=x/y;
        if(x%y)
            v[i]++;
    }
    sort(v,v+n+1);
    int q;
    f>>q;
    for(int i=1;i<=q;i++)
    {
        f>>x;
        if(x<v[1]) g<<0<<"\n";
        else if(x>v[n]) g<<n<<"\n";
            else
        g<<binsearch(x,1,n)<<"\n";
    }
    return 0;
}

----------------- PB 2443-----------------
#include <iostream>
#define N 100001
using namespace std;
int sume[N],M[N],x,s;

int cautbin(int st,int dr)
{
    if(st>dr)
        return dr;
    int mij=(st+dr)/2;
    if(sume[mij]>s||M[mij]>x)
        cautbin(st,mij-1);
    else
        cautbin(mij+1,dr);
}

int main()
{
    int n;
    cin>>n;
    int a,MAX=0;
    for(int i=1;i<=n;++i)
    {
        cin>>a;
        sume[i]=sume[i-1]+a;
        if(a>MAX)
            M[i]=MAX=a;
        else
            M[i]=MAX;
    }
    int q;
    cin>>q;
    while(q--)
        cin>>x>>s,cout<<cautbin(0,n)<<'\n';
    return 0;
}

----------------- PB 2273-----------------


#include <bits/stdc++.h>
#define nmax 200005
#define oo 2000000001
using namespace std;

int a[nmax], n;

int CautBin(int start)
{
    int j, mid, s1, s2, st, dr, dif = oo;
    st = start; j = dr = n - 1;
    while (st <= dr)
    {
        mid = (st + dr) / 2;
        s1 = a[mid] - a[start - 1];
        s2 = a[n] - a[mid];
        if (s1 < s2)
        {
            if (dif > s2 - s1)
            {
                dif = s2 - s1;
                j = mid;
            }
            st = mid + 1;
        }
        else
        {
            if (dif > s1 - s2)
            {
                dif = s1 - s2;
                j = mid;
            }
            dr = mid - 1;
        }
    }
    return j;
}

inline int Min(int x, int y, int z)
{
    return min(min(x, y), z);
}

inline int Max(int x, int y, int z)
{
    return max(max(x, y), z);
}

int main()
{
    int i, j, difmin, P, Q, X, Y, Z, d;
    /// citire
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];

    /// sume partiale
    for (i = 2; i <= n; i++)
        a[i] += a[i - 1];

    /// pentru fiecare i=1..n-2 caut binar pozitia lui j
    P = 1; Q = 2;
    X = a[1]; Y = a[2] - a[1]; Z = a[n] - a[2];
    difmin = Max(X, Y, Z) - Min(X, Y, Z);
    for (i = 1; i <= n - 2; i++)
    {
        j = CautBin(i + 1);
        X = a[i];
        Y = a[j] - a[i];
        Z = a[n] - a[j];
        d = Max(X, Y, Z) - Min(X, Y, Z);
        if (d < difmin)
        {
            difmin = d;
            P = i; Q= j;
        }
    }

    /// afisare
    cout << P << " " << Q << "\n";

    return 0;
}

----------------- PB 661-----------------

#include <iostream>
using namespace std;

int n, a[1005];

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i];

    int cnt = 0;
    for(int i = 1 ; i < n ; ++i)
        for(int j = i + 1 ; j <= n ; j ++)
            if(a[i] > a[j])
            {
                int aux = a[i];
                a[i] = a[j];
                a[j] = aux;
            }

    for(int i = 1 ; i <= n - 2  ; ++i)
        for(int j = i + 1 ; j <= n - 1; j ++)
        {
            //caut cel mai din dreapta k astfel incat a[i] + a[j] > a[k]
            int st = j + 1, dr = n,k;
            while(st <= dr)
            {
                k = (st + dr) / 2;
                if(a[i] + a[j] > a[k])
                    st = k + 1;
                else
                    dr = k - 1;
            }
                cnt += dr - j;
        }
    cout << cnt << endl;
    return 0;
}

----------------- PB 2239-----------------

#include <iostream>
#include <algorithm>
using namespace std;
int cautbin(int a[], int st, int dr, int x)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(a[m]==x)
            return m;
        else
            if(x<a[m])
                dr=m-1;
            else
                st=m+1;
    }
    return 0;
}

int main()
{
    int p[31],a[100001],n,i,j,nr=0,y,poz,k;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    p[0]=1;
    for(i=1;i<=30;i++)
        p[i]=p[i-1]*2;
    for(i=1;i<n;i++)
    {
        for(j=1;j<=30;j++)
        {
            int s=p[j]-a[i];
            if(s>=a[i])
            {
                poz=cautbin(a,i+1,n,s);
                if(poz)
                {
                    k=poz;
                while(a[k]==s&&k>i)
                    {
                        nr++;

                        k--;
                    }
                    k=poz+1;
                while(a[k]==s&&k<=n)
                    {
                        nr++;

                        k++;
                    }
                }
            }
        }
    }
    cout<<nr;
    return 0;
}

----------------- PB 2276-----------------

/**
    Complexitate O(n log n + T log n)
*/
#include <bits/stdc++.h>
#define nmax 200003
using namespace std;

int a[nmax], n;

/// cauta binar cea mai din stanga pozitie p
/// cu proprietatea ca x <= a[p]
int CautBin1(int x)
{
    if (a[n] < x) return n + 1;
    if (x <= a[1]) return 1;
    int st, dr, m, p;
    st = 1; dr = n; p = 1;
    while (st <= dr)
    {
        m = (st + dr) / 2;
        if (x <= a[m])
        {
            p = m; dr = m - 1;
        }
        else st = m + 1;
    }
    return p;
}

/// cauta binar cea mai din dreapta pozitie p
/// cu proprietatea ca a[p] <= y
int CautBin2(int y)
{
    if (a[n] <= y) return n;
    if (a[1] > y) return 0;
    int st, dr, m, p;
    st = 1; dr = n; p = 1;
    while (st <= dr)
    {
        m = (st + dr) / 2;
        if (a[m] <= y)
        {
            p = m; st = m + 1;
        }
        else dr = m - 1;
    }
    return p;
}

int main()
{
    int i, p, q, T, x, y;
    cin >> n >> T;
    for (i = 1; i <= n; i++)
        cin >> a[i];

    sort(a + 1, a + n + 1);

    while (T--)
    {
        cin >> x >> y;
        p = CautBin1(x);
        q = CautBin2(y);
        cout << (q - p + 1) << "\n";
    }

    return 0;
}