Cod sursa(job #2764906)

Utilizator GligarEsterabadeyan Hadi Gligar Data 23 iulie 2021 13:40:06
Problema Arbori indexati binar Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

const int nmax=100000, n2max=(1<<17);

int v[2*n2max];

int solutie(int a, int b, int nod, int l, int r){
    if(a>r||b<l){
        return 0;
    }else if(a<=l&&r<=b){
        return v[nod];
    }else{
        int x=solutie(a, b, nod*2 ,l ,(l+r)/2);
        int y=solutie(a, b, nod*2+1, (l+r)/2+1, r);
        return x+y;
    }
}

int main(){
    int n,m;
    fin>>n>>m;
    int n2=1,n3=1;
    while(n2<n){
        n2*=2;
    }
    while(n3*2<=n){
        n3*=2;
    }
    for(int i=1;i<=n;i++){
        fin>>v[n2+i-1];
    }
    for(int i=n2-1;i>=1;i--){
        v[i]=v[i*2]+v[i*2+1];
    }
    for(int i=1;i<=m;i++){
        int k,a,b;
        fin>>k;
        if(k==0){
            fin>>a>>b;
            v[n2+a-1]+=b;
            for(int x=(n2+a-1)/2;x>0;x/=2){
                v[x]=v[x*2]+v[x*2+1];
            }
        }else if(k==1){
            fin>>a>>b;
            fout<<solutie(a,b,1,1,n2)<<"\n";
        }else{
            fin>>a;
            int sol=n+1;
            for(int i=n3;i>0;i/=2){
                if(sol-i>=1&&solutie(1,sol-i,1,1,n2)>=a){
                    sol-=i;
                }
            }
            if(solutie(1,sol,1,1,n2)==a){
                fout<<sol<<"\n";
            }else{
                fout<<"-1\n";
            }
        }
    }
    return 0;
}