Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- typedef long long ll;
- typedef pair <ll, int> lli;
- typedef pair <int, int> ii;
- typedef pair <pair <int, int>, int> iii;
- const ll Inf = 1000000000000000000ll;
- const int Maxn = 100005;
- int n;
- vector <int> A, B, C;
- vector <iii> byX, byY;
- lli Sum[Maxn], Dif[Maxn];
- ll res[Maxn];
- void Insert(lli BIT[], int x, lli val)
- {
- for (int i = x; i > 0; i -= i & -i) {
- BIT[i].first += val.first;
- BIT[i].second += val.second;
- }
- }
- void Insert2(lli BIT[], int x, lli val)
- {
- for (int i = x; i <= n; i += i & -i) {
- BIT[i].first += val.first;
- BIT[i].second += val.second;
- }
- }
- lli Get(lli BIT[], int x)
- {
- lli res = lli(0, 0);
- for (int i = x; i <= n; i += i & -i) {
- res.first += BIT[i].first;
- res.second += BIT[i].second;
- }
- return res;
- }
- lli Get2(lli BIT[], int x)
- {
- lli res = lli(0, 0);
- for (int i = x; i > 0; i -= i & -i) {
- res.first += BIT[i].first;
- res.second += BIT[i].second;
- }
- return res;
- }
- long long int meetingPoint(vector < long long> x,vector < long long > y) {
- n = x.size();
- for (int i = 0; i < n; i++) {
- byX.push_back(iii(ii(x[i], y[i]), i));
- byY.push_back(iii(ii(y[i], x[i]), i));
- A.push_back(x[i] + y[i]);
- B.push_back(x[i] - y[i]);
- C.push_back(y[i] - x[i]);
- }
- sort(byX.begin(), byX.end()); sort(byY.begin(), byY.end());
- sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end());
- sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end());
- sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end());
- for (int i = 0; i < byX.size(); i++) {
- int ind = lower_bound(A.begin(), A.end(), byX[i].first.first + byX[i].first.second) - A.begin() + 1;
- lli got = Get(Sum, ind);
- res[byX[i].second] += got.first - ll(got.second) * byX[i].first.second;
- Insert(Sum, ind, lli(byX[i].first.second, 1));
- ind = lower_bound(B.begin(), B.end(), byX[i].first.first - byX[i].first.second) - B.begin() + 1;
- got = Get(Dif, ind);
- res[byX[i].second] += ll(got.second) * byX[i].first.second - got.first;
- Insert(Dif, ind, lli(byX[i].first.second, 1));
- }
- fill(Sum, Sum + n + 1, lli(0, 0)); fill(Dif, Dif + n + 1, lli(0, 0));
- for (int i = byX.size() - 1; i >= 0; i--) {
- int ind = lower_bound(A.begin(), A.end(), byX[i].first.first + byX[i].first.second) - A.begin() + 1;
- lli got = Get2(Sum, ind);
- res[byX[i].second] += ll(got.second) * byX[i].first.second - got.first;
- Insert2(Sum, ind, lli(byX[i].first.second, 1));
- ind = lower_bound(B.begin(), B.end(), byX[i].first.first - byX[i].first.second) - B.begin() + 1;
- got = Get2(Dif, ind);
- res[byX[i].second] += got.first - ll(got.second) * byX[i].first.second;
- Insert2(Dif, ind, lli(byX[i].first.second, 1));
- }
- fill(Sum, Sum + n + 1, lli(0, 0)); fill(Dif, Dif + n + 1, lli(0, 0));
- for (int i = 0; i < byY.size(); i++) {
- int ind = lower_bound(A.begin(), A.end(), byY[i].first.first + byY[i].first.second) - A.begin() + 1;
- lli got = Get(Sum, ind + 1);
- res[byY[i].second] += got.first - ll(got.second) * byY[i].first.second;
- Insert(Sum, ind, lli(byY[i].first.second, 1));
- ind = lower_bound(C.begin(), C.end(), byY[i].first.first - byY[i].first.second) - C.begin() + 1;
- got = Get(Dif, ind + 1);
- res[byY[i].second] += ll(got.second) * byY[i].first.second - got.first;
- Insert(Dif, ind, lli(byY[i].first.second, 1));
- }
- fill(Sum, Sum + n + 1, lli(0, 0)); fill(Dif, Dif + n + 1, lli(0, 0));
- for (int i = byY.size() - 1; i >= 0; i--) {
- int ind = lower_bound(A.begin(), A.end(), byY[i].first.first + byY[i].first.second) - A.begin() + 1;
- lli got = Get2(Sum, ind - 1);
- res[byY[i].second] += ll(got.second) * byY[i].first.second - got.first;
- Insert2(Sum, ind, lli(byY[i].first.second, 1));
- ind = lower_bound(C.begin(), C.end(), byY[i].first.first - byY[i].first.second) - C.begin() + 1;
- got = Get2(Dif, ind - 1);
- res[byY[i].second] += got.first - ll(got.second) * byY[i].first.second;
- Insert2(Dif, ind, lli(byY[i].first.second, 1));
- }
- ll ans = Inf;
- for (int i = 0; i < n; i++)
- ans = min(ans, res[i]);
- return ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement