Cod sursa(job #2425972)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 25 mai 2019 15:29:56
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.37 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, k, T, q, arb[101][4000000], sum, sum2;
struct as{

    int x, y, z, p, X, Y, Z, P;

};
vector <as> v;

void Update(int nod, int l1, int l2, int c1, int c2, int h1, int h2, int x, int y, int z, int t, int val)
{
    if(l1 == l2 && c1 == c2 && h1 == h2)
    {
        for(int i = t; i <= T; i++)
            arb[i][nod] += val;
        return;
    }
    int midh = (h1+h2)/2;
    int midl = (l1+l2)/2;
    int midc = (c1+c2)/2;
    if(z <= midh)
    {
        if(y <= midc)
        {
            if(x <= midl)
                Update(8*nod, l1, midl, c1, midc, h1, midh, x, y, z, t, val);
            else
                 Update(8*nod+1, midl+1, l2, c1, midc, h1, midh, x, y, z, t, val);
        }
        else
        {
            if(x <= midl)
                Update(8*nod+2, l1, midl, midc+1, c2, h1, midh, x, y, z, t, val);
            else
                 Update(8*nod+3, midl+1, l2, midc+1, c2, h1, midh, x, y, z, t, val);
        }
    }
    else
        {

            if(y <= midc)
            {
                if(x <= midl)
                    Update(8*nod+4, l1, midl, c1, midc, midh+1, h2, x, y, z, t, val);
                else
                     Update(8*nod+5, midl+1, l2, c1, midc, midh+1, h2, x, y, z, t, val);
            }
            else
            {
                if(x <= midl)
                    Update(8*nod+6, l1, midl, midc+1, c2, midh+1, h2, x, y, z, t, val);
                else
                     Update(8*nod+7, midl+1, l2, midc+1, c2, midh+1, h2, x, y, z, t, val);
            }
        }
        for(int i = t; i <= T; i++)
        {
            int d = 0;
            for(int po = 0; po < 8; po++)  d += arb[i][8*nod+po];

            arb[i][nod] = d;
        }
}

void Query(int nod, int l1, int l2, int c1, int c2, int h1, int h2, int x, int y, int z, int X, int Y, int Z, int t)
{
    if(l1 >= x && l1 <= X && c1 >= y && c2 <= Y && h1 >= z && h2 <= Z)
    {
        sum += arb[t][nod];
        return;
    }

     int midh = (h1+h2)/2;
    int midl = (l1+l2)/2;
    int midc = (c1+c2)/2;
    if(z <= midh)
    {
        if(y <= midc)
        {
            if(x <= midl)
                Query(8*nod, l1, midl, c1, midc, h1, midh, x, y, z, X, Y, Z, t);
            if(midl < X)
                 Query(8*nod+1, midl+1, l2, c1, midc, h1, midh, x, y, z, X, Y, Z, t);
        }
        if(midc < Y)
        {
            if(x <= midl)
                Query(8*nod+2, l1, midl, midc+1, c2, h1, midh, x, y, z, X, Y, Z, t);
            if(midl < X)
                Query(8*nod+3, midl+1, l2, midc+1, c2, h1, midh, x, y, z, X, Y, Z, t);
        }
    }
    if(midh < Z)
        {

            if(y <= midc)
            {
                if(x <= midl)
                   Query(8*nod+4, l1, midl, c1, midc, midh+1, h2, x, y, z, X, Y, Z, t);
                if(midl < X)
                    Query(8*nod+5, midl+1, l2, c1, midc, midh+1, h2, x, y, z, X, Y, Z, t);
            }
            if(midc < Y)
            {
                if(x <= midl)
                    Query(8*nod+6, l1, midl, midc+1, c2, midh+1, h2, x, y, z, X, Y, Z, t);
                if(midl < X)
                     Query(8*nod+7, midl+1, l2, midc+1, c2, midh+1, h2, x, y, z, X, Y, Z, t);
            }
        }
}

int main()
{
    fin >> q >> n >> m >> k >> T;

    for(int i = 1; i <= q; i++)
    {
        int o;
        fin >> o;
        if(o == 1)
        {
            int x, y, z, t, val;
            fin >> x >> y >> z >> t >> val;
            Update(1, 1,n, 1, m, 1,  k, x, y, z, t, val);
        }
        else
        {
            int x, y, z, p, X, Y, Z, P;
            fin >> x >> y >> z >> p >> X >> Y >> Z >> P;
           // v.push_back({x, y, z, p, X, Y, Z, P});

           sum = sum2 = 0;
            if(x%2==0) x--;
            if(y%2==0)y--;
            if(X%2==1)X++;
            if(Y%2==1)Y++;
            if(z%3==0)z-=2;
            if(z%3 == 2) z--;
            if(Z%3 == 1) Z+=2;
            if(Z%3 == 2) Z++;
            Query(1, 1, n, 1, m, 1, k, x,y, z, X,Y, Z, P);
            sum2 = sum;
            sum = 0;
            Query(1, 1, n, 1, m, 1, k, x, y,z, X, Y, Z, p-1);
            fout << sum2-sum << "\n";
        }
    }

    fout << sizeof(arb)/1025;
    return 0;
}