蒟蒻模板 0 pts help
查看原帖
蒟蒻模板 0 pts help
1296826
lcfollower楼主2025/7/26 07:55
# include <bits/stdc++.h>

# define int long long
# define up(i ,x ,y) for (int i = x ; i <= y; i ++)
# define dn(i ,x ,y) for (int i = x ; i >= y ;i --)
# define inf 1e18

using namespace std;

inline int read(){int s = 0 , w = 0;char c = getchar();while(!isdigit(c)){w |= (c == '-');c = getchar();}while(isdigit(c)){s = (s << 1) + (s << 3) + (c ^ 48);c = getchar();}return w ? -s : s;}
inline void write(int x){if(x < 0) putchar('-') , x = -x;if(x > 9) write(x / 10);putchar(x % 10 | 48);}
inline void writesp(int x){write(x) , putchar(' ');}
inline void writeln(int x){write(x) , putchar('\n');}

const int N = 1e5 + 10;
const double eps = 1e-9;
int m ,lst;
struct point {
//y = kx + b
//b = y - kx
  double k ,b;
  inline double function (double x) {
    return k * (x - 1) + b;
  }
  inline void init (double Y ,double K) {
    b = Y - K ,k = K;
  }
} seg[N];
int tr[N << 2];
inline bool cmp0 (int x ,int y ,double k){
  int a = seg[x].function (k) ,b = seg[y].function (k);
  if (max (a ,b) == a) return 1;
  return 0;
} inline void modify (int u ,int l ,int r ,int x) {
  int mid = ((l + r) >> 1);
  if (!tr[u]) {tr[u] = x ; return ;}
  if (cmp0 (x ,tr[u] ,mid)) swap (tr[u] ,x);
  if (l == r) return ;
  if (cmp0 (x ,tr[u] ,l)) modify (u << 1 ,l ,mid ,x);
  if (cmp0 (x ,tr[u] ,r)) modify (u << 1 | 1 ,mid + 1 ,r ,x);
} inline double query (int u ,int l ,int r ,int x) {
  if (!tr[u] || r < x || l > x) return -inf;
  int mid = ((l + r) >> 1);
  double res = seg[tr[u]].function (x);
  if (l == r) return res;
  return max (res ,max (query (u << 1 ,l ,mid ,x) ,query (u << 1 | 1 ,mid + 1 ,r ,x)));
} signed main(){
  m = read ();
  int sum_seg = 0;
  up (i ,1 ,m) {
    string op ; cin >> op;
    if (op == "Query") {
      int k = read ();
      if (!sum_seg) puts("0");
      else writeln (max (0.0 ,query (1 ,1 ,50000 ,k) / 1000));
    } else {
      double k ,y;
      cin >> y >> k;
      seg[++ sum_seg].init (y ,k);
      modify (1 ,1 ,50000 ,sum_seg);
    } 
  }
  return 0;
}
2025/7/26 07:55
加载中...