Advertisement
Guest User

Untitled

a guest
May 31st, 2016
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.39 KB | None | 0 0
  1. typedef long long ll;
  2. typedef pair <ll, int> lli;
  3. typedef pair <int, int> ii;
  4. typedef pair <pair <int, int>, int> iii;
  5.  
  6. const ll Inf = 1000000000000000000ll;
  7. const int Maxn = 100005;
  8.  
  9. int n;
  10. vector <int> A, B, C;
  11. vector <iii> byX, byY;
  12. lli Sum[Maxn], Dif[Maxn];
  13. ll res[Maxn];
  14.  
  15. void Insert(lli BIT[], int x, lli val)
  16. {
  17.     for (int i = x; i > 0; i -= i & -i) {
  18.         BIT[i].first += val.first;
  19.         BIT[i].second += val.second;
  20.     }
  21. }
  22.  
  23. void Insert2(lli BIT[], int x, lli val)
  24. {
  25.     for (int i = x; i <= n; i += i & -i) {
  26.         BIT[i].first += val.first;
  27.         BIT[i].second += val.second;
  28.     }
  29. }
  30.  
  31. lli Get(lli BIT[], int x)
  32. {
  33.     lli res = lli(0, 0);
  34.     for (int i = x; i <= n; i += i & -i) {
  35.         res.first += BIT[i].first;
  36.         res.second += BIT[i].second;
  37.     }
  38.     return res;
  39. }
  40.  
  41. lli Get2(lli BIT[], int x)
  42. {
  43.     lli res = lli(0, 0);
  44.     for (int i = x; i > 0; i -= i & -i) {
  45.         res.first += BIT[i].first;
  46.         res.second += BIT[i].second;
  47.     }
  48.     return res;
  49. }
  50.  
  51. long long int meetingPoint(vector < long long> x,vector < long long > y) {
  52.     n = x.size();
  53.     for (int i = 0; i < n; i++) {
  54.         byX.push_back(iii(ii(x[i], y[i]), i));
  55.         byY.push_back(iii(ii(y[i], x[i]), i));
  56.         A.push_back(x[i] + y[i]);
  57.         B.push_back(x[i] - y[i]);
  58.         C.push_back(y[i] - x[i]);
  59.     }
  60.     sort(byX.begin(), byX.end()); sort(byY.begin(), byY.end());
  61.     sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end());
  62.     sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end());
  63.     sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end());
  64.    
  65.     for (int i = 0; i < byX.size(); i++) {
  66.         int ind = lower_bound(A.begin(), A.end(), byX[i].first.first + byX[i].first.second) - A.begin() + 1;
  67.         lli got = Get(Sum, ind);
  68.         res[byX[i].second] += got.first - ll(got.second) * byX[i].first.second;
  69.         Insert(Sum, ind, lli(byX[i].first.second, 1));
  70.         ind = lower_bound(B.begin(), B.end(), byX[i].first.first - byX[i].first.second) - B.begin() + 1;
  71.         got = Get(Dif, ind);
  72.         res[byX[i].second] += ll(got.second) * byX[i].first.second - got.first;
  73.         Insert(Dif, ind, lli(byX[i].first.second, 1));
  74.     }
  75.    
  76.     fill(Sum, Sum + n + 1, lli(0, 0)); fill(Dif, Dif + n + 1, lli(0, 0));
  77.         for (int i = byX.size() - 1; i >= 0; i--) {
  78.         int ind = lower_bound(A.begin(), A.end(), byX[i].first.first + byX[i].first.second) - A.begin() + 1;
  79.         lli got = Get2(Sum, ind);
  80.         res[byX[i].second] += ll(got.second) * byX[i].first.second - got.first;
  81.         Insert2(Sum, ind, lli(byX[i].first.second, 1));
  82.         ind = lower_bound(B.begin(), B.end(), byX[i].first.first - byX[i].first.second) - B.begin() + 1;
  83.         got = Get2(Dif, ind);
  84.         res[byX[i].second] += got.first - ll(got.second) * byX[i].first.second;
  85.         Insert2(Dif, ind, lli(byX[i].first.second, 1));
  86.     }
  87.    
  88.     fill(Sum, Sum + n + 1, lli(0, 0)); fill(Dif, Dif + n + 1, lli(0, 0));
  89.     for (int i = 0; i < byY.size(); i++) {
  90.         int ind = lower_bound(A.begin(), A.end(), byY[i].first.first + byY[i].first.second) - A.begin() + 1;
  91.         lli got = Get(Sum, ind + 1);
  92.         res[byY[i].second] += got.first - ll(got.second) * byY[i].first.second;
  93.         Insert(Sum, ind, lli(byY[i].first.second, 1));
  94.         ind = lower_bound(C.begin(), C.end(), byY[i].first.first - byY[i].first.second) - C.begin() + 1;
  95.         got = Get(Dif, ind + 1);
  96.         res[byY[i].second] += ll(got.second) * byY[i].first.second - got.first;
  97.         Insert(Dif, ind, lli(byY[i].first.second, 1));
  98.     }
  99.    
  100.     fill(Sum, Sum + n + 1, lli(0, 0)); fill(Dif, Dif + n + 1, lli(0, 0));
  101.     for (int i = byY.size() - 1; i >= 0; i--) {
  102.         int ind = lower_bound(A.begin(), A.end(), byY[i].first.first + byY[i].first.second) - A.begin() + 1;
  103.         lli got = Get2(Sum, ind - 1);
  104.         res[byY[i].second] += ll(got.second) * byY[i].first.second - got.first;
  105.         Insert2(Sum, ind, lli(byY[i].first.second, 1));
  106.         ind = lower_bound(C.begin(), C.end(), byY[i].first.first - byY[i].first.second) - C.begin() + 1;
  107.         got = Get2(Dif, ind - 1);
  108.         res[byY[i].second] += got.first - ll(got.second) * byY[i].first.second;
  109.         Insert2(Dif, ind, lli(byY[i].first.second, 1));
  110.     }
  111.    
  112.     ll ans = Inf;
  113.     for (int i = 0; i < n; i++)
  114.         ans = min(ans, res[i]);
  115.     return ans;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement