Submission #35053588

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

using Point = std::pair<ll, ll>;
const ll INF = 0x3f3f3f3f3f3f3f3f;
Point sub(Point a,Point b){ // return a-b
  return {a.first - b.first,a.second-b.second};
}

ll cross(Point a, Point b, Point c){ // (a-b) x (c-b)
  auto [x0,y0] = sub(a,b);
  auto [x1,y1] = sub(c,b);
  return x1*y0 -x0*y1;
}

struct ConvexHull{
  std::vector<Point> lower;
  std::vector<Point> upper;
  ConvexHull(Point p): lower{p}, upper{p}{}
  ConvexHull(const ConvexHull& a, const ConvexHull& b){ // 两个凸包合并
    {
      std::vector<Point> v; // 逆时针弧
      std::merge(a.lower.begin(), a.lower.end(), b.lower.begin(), b.lower.end(), back_inserter(v)); // 本身a,b下标有序, merge 会按pair的比较的排序
      for(Point p : v){
        while(lower.size() >= 2 && cross(lower.rbegin()[1], lower.back(), p) <= 0) lower.pop_back();
        lower.push_back(p);
      }
    }
    {
      std::vector<Point> v; // 顺时针弧
      std::merge(a.upper.begin(), a.upper.end(), b.upper.begin(), b.upper.end(), back_inserter(v)); // 本身a,b下标有序, merge 会按pair的比较的排序
      for(Point p : v){
        while(upper.size() >= 2 && cross(upper.rbegin()[1], upper.back(), p) >= 0) upper.pop_back();
        upper.push_back(p);
      }
    }
  }
  ll get(ll A, ll B) const { // 凸包中 求 Ax+By 的最大值,  B > 0, max(a/bx+y) 顺时针 上凸, B < 0 min(a/bx+y) 逆时针下凸
    auto& s = B < 0 ? lower : upper;
    auto f = [&](ll i){ return A * s[i].first + B * s[i].second; };
    ll l = 0;
    ll r = s.size() - 1;
    while(r-l >= 3){ // 3分
      ll x1 = (2*l+r)/3;
      ll x2 = (l+2*r)/3;
      ll f1 = f(x1);
      ll f2 = f(x2);
      if(f1 < f2) l = x1;
      else r = x2;
    }
    ll ans = -INF;
    rep(i,l,r+1) ans = std::max(ans, f(i));
    return ans;
  }
};
int main(){
  ll Q = read(); // 2e5
  std::vector<ConvexHull> S;
  rep(i,1,Q+1){
    ll X = read();
    ll Y = read(); // + (X,Y)
    ll A = read(); //
    ll B = read(); // 查询(A,B)
    S.emplace_back(std::pair{X, Y});
    // 最低位 2的幂次 次处理, 其实就是树状数组的想法, 每个位置表示 二进制最低位对应的一断内容,现在直接收集起来
    for(int j = i; j%2==0; j/=2){
      S.rbegin()[1] = ConvexHull(S.rbegin()[1], S.back());
      S.pop_back();
    }
    ll ans = -INF;
    for(auto& s : S) ans = std::max(ans, s.get(A, B));
    printf("%lld\n",ans);
  }
}

// r/3 + 2l/3 
// 2r/3 + l/3

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:4:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    4 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result