Cod sursa(job #1222517)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 23 august 2014 14:48:18
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#define DIM 100010
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,v[DIM];

void update(int p,int x){
    for(;p<=n;p+=p&(-p)) v[p]+=x;
}

inline int query1(int p){
    int r=0;
    for(;p;p-=p&(-p))  r+=v[p];
    return r;
}

inline int query2(int a){
    int p=1,d=1;
    for(;d<=n;d*=2);
    for(;d;d/=2){
        if(p+d-1<=n && v[p+d-1]<=a){
            a-=v[p+d-1];
            if(!a) return p+d-1;
            p+=d;
        }
    }
    return -1;
}

int main(void){
    register int i,j,t,x,a,b;

    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>x,update(i,x);

    for(i=1;i<=m;i++){
        f>>t;
        switch(t){
            case 0:
                f>>a>>b;
                update(a,b);
                break;
            case 1:
                f>>a>>b;
                g<<query1(b)-query1(a-1)<<"\n";
                break;
            default:
                f>>a;
                g<<query2(a)<<"\n";
        }
    }
    return 0;
}