Cod sursa(job #2565516)

Utilizator radubigColtos Radu radubig Data 2 martie 2020 14:36:31
Problema Arbori indexati binar Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#define lim 100000

using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");

inline int len(int i){  return i-(i&(i-1)); }

int v[lim+5], aib[lim+5];
int n,m,i,tip,a,b;

inline void update(int a, int b)
{
    while(a<=n)
    {
        aib[a]+=b;
        a+=len(a);
    }
}

inline int query1(int a, int b)
{
    int sum1=0, sum2=0;
    a-=1;
    while(a>0)
    {
        sum1+=aib[a];
        a-=len(a);
    }
    while(b>0)
    {
        sum2+=aib[b];
        b-=len(b);
    }
    return sum2-sum1;
}

inline int query2(int a)
{
    int rez=0, poz=1<<20;
    while(poz>0)
    {
        if(rez+poz<=n && aib[rez+poz]<=a)
        {
            rez+=poz;
            a-=aib[rez];
        }
        poz/=2;
    }
    if(a==0) return rez;
    return -1;
}

int main()
{
    in>>n>>m;
    for(i=1;i<=n;i++)
    {
        in>>v[i];
        update(i,v[i]);
    }
    for(i=1;i<=m;i++)
    {
        in>>tip;
        if(tip==0)
        {
            in>>a>>b;
            update(a,b);
        }
        else if(tip==1)
        {
            in>>a>>b;
            out<<query1(a,b)<<'\n';
        }
        else
        {
            in>>a;
            out<<query2(a)<<'\n';
        }
    }
    return 0;
}