Cod sursa(job #2981268)

Utilizator velciu_ilincavelciu ilinca velciu_ilinca Data 17 februarie 2023 16:47:41
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.82 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("dulciuri.in");
ofstream out("dulciuri.out");

int nrlevel, lastnode;
const int nmax = 1000001;
int tree_lin[2999999];
int tree_col[2999999];

void update_lin(int pozlin, int dulce, int left = 1, int right = lastnode, int node = 1)
{
    if(left == right)
    {
        tree_lin[node] += dulce;
        return;
    }

    int med = (left + right)/2;
    if(med >= pozlin)
        update_lin(pozlin, dulce, left, med, 2*node);
    else
        update_lin(pozlin, dulce, med + 1, right, 2*node + 1);

    tree_lin[node] = tree_lin[2*node] + tree_lin[2*node + 1];
}
void update_col(int pozlin, int dulce, int left = 1, int right = lastnode, int node = 1)
{
    if(left == right)
    {
        tree_col[node] += dulce;
        return;
    }
     //out<<"Update: "<<node<<" "<<tree_col[node]<<'\n';
    int med = (left + right)/2;
    if(med >= pozlin)
        update_col(pozlin, dulce, left, med, 2*node);
    else
        update_col(pozlin, dulce, med + 1, right, 2*node + 1);

    tree_col[node] = tree_col[2*node] + tree_col[2*node + 1];
//    out<<"Update: "<<node<<" "<<tree_col[node]<<'\n';
}
int query_lin(int searchl, int searchr, int left = 1, int right = lastnode, int node = 1)
{
    int rez1 = 0;
    if(searchl <= left && searchr >= right)
        return tree_lin[node];
    int med = (left + right)/2;
    if(searchl <= med)
        rez1 += query_lin(searchl, searchr, left, med, 2*node);
    if(searchr > med)
       rez1 += query_lin(searchl, searchr, med+1, right, 2*node+1);
    return rez1;
}
int query_col(int searchl, int searchr, int left = 1, int right = lastnode, int node = 1)
{
    int rez = 0;

    //out<<"Query1: "<<left<<" "<<right<<" "<<searchr<<" "<<node<<'\n';
    if(searchl <= left && searchr >= right){
        //out<<"Node: "<<node<<'\n';
        return tree_col[node];
    }
    int med = (left + right)/2;
    //out<<"Query2: "<<left<<" "<<right<<" "<<med<<" "<<rez<<'\n';
    if(searchl <= med)
        rez += query_col(searchl, searchr, left, med, 2*node);
    if(searchr > med)
        rez += query_col(searchl, searchr, med+1, right, 2*node+1);
    return rez;
}
int main()
{
    nrlevel = log2(nmax);
    nrlevel += ((1<<nrlevel) < nmax);
    lastnode = (1<<nrlevel);

    int q;
    in>>q;
    for(int k=1; k<=q; k++)
    {
        int type;
        in>>type;
        if(type == 1)
        {
            int coloana, dulce;
            in>>coloana>>dulce;
            coloana++;
            update_col(coloana,dulce);
        }
        else if(type == 2)
        {
            int linie, dulce;
            in>>linie>>dulce;
            linie++;
            update_lin(linie,dulce);
        }
        else
        {
            int stx, sty, drx, dry;
            in>>stx>>drx>>sty>>dry;
            stx++;
            drx++;
            sty++;
            dry++;
            if(stx > sty)
                swap(stx,sty);
            if(drx > dry)
                swap(drx,dry);

            int fragment_col = sty - stx ;
            int fragment_lin = dry - drx ;

            if(fragment_lin == 0)
                fragment_lin = 1;
            if(fragment_col == 0)
                fragment_col = 1;

            //float time_lin = (float) 1/fragment_lin;
            //float time_col = (float) 1/fragment_col;
            //out<<time_col<<" "<<time_lin<<'\n';

            double Llin = 0;
            double Lcol = 0;


            Llin = (double)query_lin(drx,dry-1)/fragment_lin;
            Lcol = (double)query_col(stx ,sty-1)/fragment_col;
            //out<<Llin<<" "<<Lcol<<'\n';

            //Llin = Llin * time_lin;
            //Lcol = Lcol * time_col;
            out << fixed << setprecision(10) << Llin + Lcol << "\n";
        }
    }
    return 0;
}