fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef int num_t;
  5. const num_t oo = (num_t) 1e9;
  6. struct func_t {
  7.     num_t a, b;
  8.     func_t(num_t a = 0, num_t b = oo) : a(a), b(b) {}
  9.     num_t query(num_t x) {return a * x + b;}
  10. };
  11. struct node_t {
  12.     node_t *l, *r;
  13.     func_t f;
  14.     node_t(node_t* l = 0, node_t* r = 0, func_t f = func_t()) : l(l), r(r), f(f) {}
  15.     num_t query(num_t x) {return f.query(x);}
  16. };
  17. node_t* upd(node_t* p, int l, int r, int L, int R, func_t f) {
  18.     if (l > R || r < L) return p;
  19.     int M = L + (R - L >> 1);
  20.     node_t* res = p ? new node_t(p->l, p->r, p->f) : new node_t();
  21.     if (l <= L && r >= R) {
  22.         int fl = f.query(L) >= (p ? p->query(L) : oo);
  23.         int fr = f.query(R) >= (p ? p->query(R) : oo);
  24.         if (fl && fr) return res;
  25.         if (!fl && !fr) {
  26.             res->f = f;
  27.             return res;
  28.         }
  29.         int fm1 = f.query(M) >= (p ? p->query(M) : oo);
  30.         if (fl && fm1) {
  31.             res->r = upd(res->r, l, r, M + 1, R, f);
  32.             return res;
  33.         }
  34.         if (!fl && !fm1) {
  35.             res->r = upd(res->r, l, r, M + 1, R, res->f);
  36.             res->f = f;
  37.             return res;
  38.         }
  39.         int fm2 = f.query(M + 1) >= (p ? p->query(M + 1) : oo);
  40.         if (fm2 && fr) {
  41.             res->l = upd(res->l, l, r, L, M, f);
  42.             return res;
  43.         }
  44.         if (!fm2 && !fr) {
  45.             res->l = upd(res->l, l, r, L, M, res->f);
  46.             res->f = f;
  47.             return res;
  48.         }
  49.         assert(0);
  50.     }
  51.     res->l = upd(res->l, l, r, L, M, f);
  52.     res->r = upd(res->r, l, r, M + 1, R, f);
  53.     return res;
  54. }
  55. node_t* upd(node_t* p, int l, int r, int L, int R, num_t a, num_t b) {
  56.     return upd(p, l, r, L, R, func_t(a, b));
  57. }
  58. num_t query(node_t* p, int i, int L, int R) {
  59.     if (!p) return oo;
  60.     if (i < L || i > R) return oo;
  61.     num_t res = p->query(i);
  62.     if (L < R) {
  63.         res = min(res, query(p->l, i, L, L + R >> 1));
  64.         res = min(res, query(p->r, i, (L + R >> 1) + 1, R));
  65.     }
  66.     return res;
  67. }
  68.  
  69. int main() {
  70.     return 0;
  71. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/jzz1jn
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!