Competition - Qualifications - E - Matrix distance 2 types of query: 


add value to x y
output the sum of \$value*(|a - x|+|b-y|)\$ for every pair(a, b, v).


In the start you are given \$n\$ (number of querys), \$m\$ (maximal dimension for square matrix). 

In the next \$n\$ lines you are given either:


1 x y v, you should add value v to x y coordinate, or
2 x y calculate the \$distance * value\$ between every \$a\$ and \$b\$ that have some values (distance is being calculated: \$|a- x| + |b - y|\$). So the formula for one spot in matrix would be \$v * (|a - x| + |b - y|)\$ for a given \$a\$ and \$b\$.


My code works, but it is too slow.

Constraints: 
\$n &lt;= 250'000\$
\$m &lt;= 10^9\$
\$X_i\$ and \$Y_i &lt;= m\$
\$V_i\$ &lt;= \$10^4\$

time limit: 2.5s

My code:

for (int i = 0; i &lt; n; ++i){

    int el;
    cin &gt;&gt; el;

    if (el == 1){
        int a, b, c;
        cin &gt;&gt; a &gt;&gt; b &gt;&gt; c;

        x.push_back(a);
        y.push_back(b);
        v.push_back(c);
    }

    if (el == 2){
        int a, b;
        cin &gt;&gt; a &gt;&gt; b;

        ll sol = 0; 
        for (int j = 0; j &lt; x.size(); ++j){
            sol += v[j] * (abs(a - x[j]) + abs(b - y[j]));
        }
        cout &lt;&lt; sol &lt;&lt; "\n";

    }

}
Your explanation is difficult to follow, but your code explains it. It's simple and clear.
The main thing I want to advise is to not use using namespace std. See this Stack Overflow question for reasons.
You don't show what ll is, I presume it's a long long int type?
For a newline, use '\n' rather than &quot;\n&quot;. There's not a huge difference, but it's slightly faster to output a single character than a string containing a single character.
In terms of improving performance, you might want to keep a single vector with a struct:
struct Data {
   int x, y, v;
}
std::vector&lt;Data&gt; data;
// ...
data.emplace_back(a, b, c);

This gives you at least two advantages:

You call malloc/realloc (on push_back) three times as frequently if you have three vectors. If you have only one vector on the stack, there is a good possibility that realloc will simply add space to the end of your block, rather than creating a new block and copying the data over. If you have three vectors, trying to expand one will invariably have another be in the way, forcing the copy.
Of course you could do data.reserve(n) and be sure you'll never call realloc.

Data locality: In your second case, where you iterate over the data, you would read the three values from consecutive locations in memory, rather than from disjoint locations. This will allow a better use of cache. Since you iterate over these frequently, it could make a big difference.


Finally, you can improve your distance computation and do away with one of the calls to std::abs. Note that, for the L-1 norm that you use, distance(p1,p2) == abs(distance(0,p1)-distance(0,p2)). And, given your text &quot;m (maximal dimension for square matrix)&quot;, I presume that the coordinates indicate a location within this matrix, and therefore are always larger or equal to 0. If so, computing the distance to the origin requires no std::abs. then your distance
abs(a - x[j]) + abs(b - y[j]) // distance(p1,p2)

can be rewritten as
abs(a + b - (x[j] + y[j])) // abs(distance(0,p1)-distance(0,p2))

The thing that still bothers me is that you are given m, but you don't need it. Maybe we're missing another possibility for optimization there?

(EDIT) Reducing complexity from O(n²) to O(n log n)
It is possible to reduce the complexity of step 2 by adding some (a lot of) complexity to step 1. Both steps (adding a point and computing the weighted distance of a point to all previous points) should turn into operations of logarithmic complexity w.r.t. the number of points seen so far.
We start with the observation that the core distance computation
sum( v[j] * ( abs(a - x[j]) + abs(b - y[j]) ) )

can we rewritten as
sum(v[j] * abs(a - x[j])) + sum(v[j] * abs(b - y[j]))

That is, the two dimensions can be tackled independently. From here on we'll look only at the x-coordinate, and presume we repeat the same operations for the y-coordinate.
Next, we note that we can write
sum(v[j] * abs(a - x[j])) == sum(v[j] * (a - x[j])) // for x[j]&lt;=a
                          == sum(v[j] * (x[j]) - a) // for x[j]&gt;=a

Thus, we need to separate incoming points in step 1 into those that are to the left of a future query point, and those to the right. (Note that if x[j]==a, the distance will be 0, and the point can be ignored or used twice without affecting the output.
So how do we separate incoming points around a coordinate we don't know yet? Use a tree. R-trees are the tool for spatial indexing like this. We need a simplified version, since we don't need to store bounding boxes, only split locations. Maybe it's more similar to a quadree.
Because
sum(v[j] * (a - x[j])) == sum(v[j])*a - sum(v[j]*x[j])

it seems that we need to accumulate sum(v) and sum(v*x) for all points to the left of x (and also for those to the right). Thus our tree needs to store these values. The tree further needs to indicate what the coordinate is that splits its left and right branches. Thus, we can easily find in the tree the nodes that are to the left or to the right when computing a distance in step 2.
I think the tree should have each input point as a leaf node. Each non-leaf node (can I call those branch nodes?) would contain the sum of v and v*x for its two children, as well as the x-coordinate half-way between the two children's x-coordinates. Something like this:
struct Node {
  Node* left;
  Node* right;
  std::uint64 sumV;
  std::uint64 sumXV;
  std::uint32 x;
}

During step 1, it's simply a matter of inserting nodes:
void Node::insert(std::uint32 x, std::uint32 v) {
  if (isLeaf()) {
    // turn this leaf node into a branch node
    // create a new leaf node with {sumV,sumXV,x}
    // create a new leaf node with {v,x*v,x}
    sumV = left-&gt;sumV + right-&gt;sumV;
    sumXV = left-&gt;sumXV + right-&gt;sumXV;
    x = (left-&gt;x + right-&gt;x) / 2;
  }
  if (x &lt;= node-&gt;x) {
    left-&gt;insert(x,v);
  } else {
    right-&gt;insert(x,v);
  }
}

During step 2, find the position of a in the tree, and obtain sumV and sumXV for all nodes to the left, and all those to the right:
std::uint64 Node::sum(std::uint32 a) {
  if (isLeaf()) {
    return std::abs(sumV*a - sumVX);
  }
  if (a&gt;=x) {
    return left-&gt;sumV*a - left-&gt;sumXV + right-&gt;sum(a);
  } else {
    return right-&gt;sumXV - right-&gt;sumV*a + left-&gt;sum(a);
  }
}

I don't have time to write a full implementation and test it, but it was to think about this problem!