Cod sursa(job #3151001)

Utilizator vlad_miscociMiscoci Vlad Andrei vlad_miscoci Data 19 septembrie 2023 12:36:02
Problema Arbori indexati binar Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>

using namespace std;
int N;
vector<int> bit(150001, 0);
vector<int> v;
ifstream cin("aib.in");
ofstream cout("aib.out");
void update(int i, int val)
{
    while(i <= N)
    {
        bit[i] += val;
        i += i & -i;
    }
}
int prefixsum(int i)
{
    int sum=0;
    while( i > 0)
    {
        sum += bit[i];
        i -= i & -i;
    }
    return sum;
}
int rangesum(int i, int j)
{
    return prefixsum(j) - prefixsum(i-1);
}
int main()
{
    int x, m, op, a, b;
    cin >> N >> m;
    v.push_back(0);
    for(int i=1; i<=N; i++)
    {
        cin >> x;
        v.push_back(x);
        update(i, x);
    }
    for(int i=0; i<m; i++)
    {
        cin >> op;
        if(op == 0){
                cin >> a >> b;
            update(a, b);
        }
        else if(op==1){
                cin >> a >> b;
            cout << rangesum(a,b) << '\n';
        }
        else if(op == 2)
        {
            cin >> a;
            int sum = -1, poz=0, ok=0;
            do
            {
                poz++;
                sum = rangesum(1, poz);
                if(sum == a)
                {
                    ok=1;
                }
            }while(sum < a);
            if(ok == 1)
                cout << poz << '\n';
            else
                cout << -1 << '\n';
        }
    }
    return 0;
}