Cod sursa(job #2498325)

Utilizator 0738076326Simon Wil 0738076326 Data 23 noiembrie 2019 19:45:43
Problema Arbori indexati binar Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5 + 10;
int n,m,aib[NMAX];

void add(int val, int pos){

    while(pos <= n){

        aib[pos] += val;
        pos += pos & -pos;

    }

}

int sum(int pos){
    int sum = 0;

    while(pos > 0){

        sum += aib[pos];
        pos -= pos & -pos;

    }

    return sum;
}

int position(int value){
    int step,i;

    for(step = 1 ; step < n ; step <<= 1);

    for(i = 0 ; step > 0 ; step >>= 1){

        if(i + step <= n){

            if(aib[i + step] <= value){
                i += step;
                value -= aib[i];
            }

            if(!value && i)
                return i;

        }

    }
    return -1;

}

int main(){
    int i,type,x,y;
    f >> n >> m;
    for(i = 1 ; i <= n ; i++){
        f >> x;
        add(x,i);
    }

    while(m--){

        f >> type;

        if(type == 0){

            f >> x >> y;
            add(y, x);

        }else
            if(type == 1){

                f >> x >> y;
                g << sum(y) - sum(x - 1) << "\n";

            }else{

                f >> x;
                g << position(x) << "\n";

            }
    }

    return 0;
}