Submission #520380

#	Time	Username	Problem	Language	Result	Execution time	Memory
520380		Alex_tz307	Weirdtree (RMI21_weirdtree)	C++17	Compilation error	0 ms	0 KiB

weirdtree

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

struct node {
  int64_t sum;
  int max1, cntMax, max2;

  node operator + (const node &rhs) const {
    node ans;
    ans.sum = sum + rhs.sum;
    ans.max1 = max(max1, rhs.max1);
    ans.max2 = max(max2, rhs.max2);
    if (max1 < rhs.max1) {
      ans.cntMax = rhs.cntMax;
      maxSelf(ans.max2, max1);
    } else if (rhs.max1 < max1) {
      ans.cntMax = cntMax;
      maxSelf(ans.max2, rhs.max1);
    } else {
      ans.cntMax = cntMax + rhs.cntMax;
    }
    return ans;
  }
} NIL{0, 0, 0, -INF};

struct ST {
  int n, dim = 1;
  vector<node> t;

  ST(int N) : n(N) {
    while (dim < n) {
      dim *= 2;
    }
    dim *= 2;
    t.resize(dim);
  }

  void setVal(int x, int v) {
    t[x].sum = t[x].max1 = v;
    t[x].cntMax = 1;
    t[x].max2 = -INF;
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      int v;
      cin >> v;
      setVal(x, v);
      return;
    }
    int mid = (lx + rx) / 2;
    build(x * 2, lx, mid);
    build(x * 2 + 1, mid + 1, rx);
    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void updateNode(int x, int v) {
    t[x].sum += (int64_t)(v - t[x].max1) * t[x].cntMax;
    t[x].max1 = v;
  }

  void push(int x) {
    for (int i = 0; i < 2; ++i) {
      int son = x * 2 + i;
      if (dim <= son) {
        return;
      }
      if (t[x].max1 < t[son].max1) {
        updateNode(son, t[x].max1);
      }
    }
  }

  void update(int x, int lx, int rx, int st, int dr, int &extra, int v) {
    if (t[x].max1 <= v - (extra > 0)) {
      return;
    }
    if (st <= lx && rx <= dr && t[x].max2 < v - (extra > 0) && (extra == 0 || extra >= t[x].cntMax)) {
      updateNode(x, v - (extra > 0));
      if (extra > 0) {
        extra -= t[x].cntMax;
      }
      return;
    }
    push(x);
    int mid = (lx + rx) / 2;
    if (st <= mid) {
      update(x * 2, lx, mid, st, dr, extra, v);
    }
    if (mid < dr) {
      update(x * 2 + 1, mid + 1, rx, st, dr, extra, v);
    }
    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void update(int st, int dr, int extra, int v) {
    update(1, 1, n, st, dr, extra, v);
  }

  void cut(int st, int dr, int k) {
    while (k > 0) {
      node ans = query(st, dr);
      if (ans.max1 == 0) {
        return;
      }
      int64_t cutMax = (int64_t)ans.cntMax * (ans.max1 - ans.max2);
      if (cutMax <= k) {
        update(st, dr, 0, ans.max2);
        k -= cutMax;
      } else {
        update(st, dr, k % ans.cntMax, ans.max1 - k / ans.cntMax);
        k = 0;
      }
    }
  }

  void setPos(int x, int lx, int rx, int pos, int v) {
    if (lx == rx) {
      setVal(x, v);
      return;
    }
    push(x);
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      setPos(x * 2, lx, mid, pos, v);
    } else {
      setPos(x * 2 + 1, mid + 1, rx, pos, v);
    }
    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void setPos(int pos, int v) {
    setPos(1, 1, n, pos, v);
  }

  node query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x];
    }
    push(x);
    int mid = (lx + rx) / 2;
    node left = NIL, right = NIL;
    if (st <= mid) {
      left = query(x * 2, lx, mid, st, dr);
    }
    if (mid < dr) {
      right = query(x * 2 + 1, mid + 1, rx, st, dr);
    }
    return left + right;
  }

  node query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
};

void testCase() {
  int n, q;
  cin >> n >> q;
  ST t(n);
  t.build(1, 1, n);
  for (int i = 0; i < q; ++i) {
    char op;
    cin >> op;
    if (op == '1') {
      int l, r, k;
      cin >> l >> r >> k;
      t.cut(l, r, k);
    } else if (op == '2') {
      int pos, v;
      cin >> pos >> v;
      t.setPos(pos, v);
    } else {
      int l, r;
      cin >> l >> r;
      cout << t.query(l, r).sum << '\n';
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cceYJ0ph.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc7Dlr9h.o:weirdtree.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cceYJ0ph.o: in function `main':
grader.cpp:(.text.startup+0xe2): undefined reference to `initialise(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x122): undefined reference to `inspect(int, int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x263): undefined reference to `magic(int, int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x28e): undefined reference to `cut(int, int, int)'
collect2: error: ld returned 1 exit status