oj.uz

Submission #520384

# Submission time Handle Problem Language Result Execution time Memory
520384 2022-01-29T18:23:17 Z Alex_tz307 Weirdtree (RMI21_weirdtree) C++17
100 / 100
 371 ms 37316 KB 
#include <bits/stdc++.h>
#include "weirdtree.h"
#define INF 0x3f3f3f3f

using namespace std;

const int kN = 3e5;
int a[1 + kN];

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;

  void init(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) {
      setVal(x, a[lx]);
      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);
  }
} t;

void initialise(int N, int Q, int h[]) {
  for (int i = 1; i <= N; ++i) {
    a[i] = h[i];
  }
  t.init(N);
  t.build(1, 1, N);
}

void cut(int l, int r, int k) {
  t.cut(l, r, k);
}

void magic(int i, int x) {
  t.setPos(i, x);
}

long long int inspect(int l, int r) {
  return t.query(l, r).sum;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 63 ms 9556 KB Output is correct
4 Correct 63 ms 9436 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 371 ms 37240 KB Output is correct
4 Correct 344 ms 37316 KB Output is correct
5 Correct 362 ms 37096 KB Output is correct
6 Correct 348 ms 36992 KB Output is correct
7 Correct 10 ms 9272 KB Output is correct
8 Correct 33 ms 8864 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9272 KB Output is correct
2 Correct 33 ms 8864 KB Output is correct
3 Correct 100 ms 28740 KB Output is correct
4 Correct 116 ms 28900 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 63 ms 9556 KB Output is correct
4 Correct 63 ms 9436 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 10 ms 9272 KB Output is correct
8 Correct 33 ms 8864 KB Output is correct
9 Correct 59 ms 9448 KB Output is correct
10 Correct 63 ms 9496 KB Output is correct
11 Correct 57 ms 9480 KB Output is correct
12 Correct 69 ms 9600 KB Output is correct
13 Correct 62 ms 9540 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 63 ms 9556 KB Output is correct
4 Correct 63 ms 9436 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 371 ms 37240 KB Output is correct
8 Correct 344 ms 37316 KB Output is correct
9 Correct 362 ms 37096 KB Output is correct
10 Correct 348 ms 36992 KB Output is correct
11 Correct 100 ms 28740 KB Output is correct
12 Correct 116 ms 28900 KB Output is correct
13 Correct 59 ms 9448 KB Output is correct
14 Correct 63 ms 9496 KB Output is correct
15 Correct 57 ms 9480 KB Output is correct
16 Correct 69 ms 9600 KB Output is correct
17 Correct 62 ms 9540 KB Output is correct
18 Correct 10 ms 9272 KB Output is correct
19 Correct 33 ms 8864 KB Output is correct
20 Correct 281 ms 36224 KB Output is correct
21 Correct 298 ms 36804 KB Output is correct
22 Correct 310 ms 36584 KB Output is correct
23 Correct 304 ms 36648 KB Output is correct
24 Correct 281 ms 36416 KB Output is correct