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 valuev
tox y
coordinate, or2 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 <= 250’000$
$ m <= 10^9$
$ X_i$ and $ Y_i <= m$
$ V_i$ <= $ 10^4$
time limit: 2.5s
My code:
for (int i = 0; i < n; ++i){ int el; cin >> el; if (el == 1){ int a, b, c; cin >> a >> b >> c; x.push_back(a); y.push_back(b); v.push_back(c); } if (el == 2){ int a, b; cin >> a >> b; ll sol = 0; for (int j = 0; j < x.size(); ++j){ sol += v[j] * (abs(a - x[j]) + abs(b - y[j])); } cout << sol << "\n"; } }