oj.uz

Submission #685141

# Submission time Handle Problem Language Result Execution time Memory
685141 2023-01-23T15:04:51 Z tvladm2009 Weirdtree (RMI21_weirdtree) C++14
100 / 100
 714 ms 37372 KB 
#include <bits/stdc++.h>
#include "weirdtree.h"

using namespace std;

typedef long long ll;
const int N = (int) 3e5 + 7;
int a[N];
int n, q;

struct Node {
  int max1;
  int max2;
  int cnt;
  ll sum;
};

Node operator + (const Node &a, const Node &b) {
  Node aux;
  aux.sum = a.sum + b.sum;
  if (a.max1 == b.max1) {
    aux.max1 = a.max1;
    aux.cnt = a.cnt + b.cnt;
    aux.max2 = max(a.max2, b.max2);
  } else if (a.max1 < b.max1) {
    aux.max1 = b.max1;
    aux.cnt = b.cnt;
    aux.max2 = max(a.max1, b.max2);
  } else {
    aux.max1 = a.max1;
    aux.cnt = a.cnt;
    aux.max2 = max(b.max1, a.max2);
  }
  return aux;
}

Node segt[4 * N];

void baga(int v, int val) {
  if (segt[v].max1 <= val) return;
  segt[v].sum -= (ll)segt[v].max1 * segt[v].cnt;
  segt[v].max1 = val;
  segt[v].sum += (ll)segt[v].max1 * segt[v].cnt;
}

void push(int v, int tl, int tr) {
  if (tl < tr) {
    int tm = (tl + tr) / 2;
    baga(2 * v, segt[v].max1);
    baga(2 * v + 1, segt[v].max1);
  }
}

void build(int v, int tl, int tr) {
  if (tl == tr) {
    segt[v] = {a[tl], 0, 1, a[tl]};
  } else {
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    segt[v] = segt[2 * v] + segt[2 * v + 1];
  }
}

void update(int v, int tl, int tr, int x, int y, int val) {
  push(v, tl, tr);
  if (segt[v].max1 <= val) return;
  if (x <= tl && tr <= y && segt[v].max2 < val) {
    baga(v, val);
    return;
  }
  int tm = (tl + tr) / 2;
  if (x <= tm) {
    update(2 * v, tl, tm, x, min(tm, y), val);
  }
  if (tm + 1 <= y) {
    update(2 * v + 1, tm + 1, tr, max(x, tm + 1), y, val);
  }
  segt[v] = segt[2 * v] + segt[2 * v + 1];
}

void update2(int v, int tl, int tr, int pos, int val) {
  push(v, tl, tr);
  if (tl == tr) {
    segt[v] = {val, 0, 1, val};
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm) {
    update2(2 * v, tl, tm, pos, val);
  } else {
    update2(2 * v + 1, tm + 1, tr, pos, val);
  }
  push(2 * v, tl, tm);
  push(2 * v + 1, tm + 1, tr);
  segt[v] = segt[2 * v] + segt[2 * v + 1];
}

Node query(int v, int tl, int tr, int x, int y) {
  push(v, tl, tr);
  if (x <= tl && tr <= y) {
    return segt[v];
  }
  int tm = (tl + tr) / 2;
  if (x <= tm && y <= tm) {
    return query(2 * v, tl, tm, x, y);
  } else if (tm + 1 <= x && tm + 1 <= y) {
    return query(2 * v + 1, tm + 1, tr, x, y);
  } else {
    return query(2 * v, tl, tm, x, tm) + query(2 * v + 1, tm + 1, tr, tm + 1, y);
  }
}

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

void cut(int l, int r, int k) {
  while (k > 0) {
    Node res = query(1, 1, n, l, r);
    if (res.max1 == 0) {
      break;
    }
    if ((ll)(res.max1 - res.max2) * res.cnt <= k) {
      k -= (ll)(res.max1 - res.max2) * res.cnt;
      update(1, 1, n, l, r, res.max2);
      continue;
    }

    int full = k / res.cnt;
    int partial = k % res.cnt;
    if (full > 0) update(1, 1, n, l, r, res.max1 - full);
    if (partial > 0) {
      int low = l, high = r, sol = 0;
      while (low <= high) {
        int mid = (low + high) / 2;
        Node aux = query(1, 1, n, l, mid);
        if (aux.max1 == res.max1 - full && aux.cnt == partial) {
          sol = mid;
          break;
        }
        if (aux.max1 < res.max1 - full || aux.cnt < partial) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      update(1, 1, n, l, sol, res.max1 - full - 1);
    }
    break;
  }
}

void magic(int pos, int val) {
  update2(1, 1, n, pos, val);
}

ll inspect(int l, int r) {
  Node res = query(1, 1, n, l, r);
  return res.sum;
}

Compilation message

weirdtree.cpp: In function 'void push(int, int, int)':
weirdtree.cpp:48:9: warning: unused variable 'tm' [-Wunused-variable]
   48 |     int tm = (tl + tr) / 2;
      |         ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 75 ms 9544 KB Output is correct
4 Correct 93 ms 9432 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 356 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 714 ms 37232 KB Output is correct
4 Correct 323 ms 37372 KB Output is correct
5 Correct 701 ms 37108 KB Output is correct
6 Correct 306 ms 37072 KB Output is correct
7 Correct 13 ms 9336 KB Output is correct
8 Correct 179 ms 8968 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9336 KB Output is correct
2 Correct 179 ms 8968 KB Output is correct
3 Correct 165 ms 35640 KB Output is correct
4 Correct 275 ms 35984 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 75 ms 9544 KB Output is correct
4 Correct 93 ms 9432 KB Output is correct
5 Correct 3 ms 356 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 13 ms 9336 KB Output is correct
8 Correct 179 ms 8968 KB Output is correct
9 Correct 55 ms 9436 KB Output is correct
10 Correct 93 ms 9408 KB Output is correct
11 Correct 60 ms 9488 KB Output is correct
12 Correct 101 ms 9540 KB Output is correct
13 Correct 59 ms 9560 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 75 ms 9544 KB Output is correct
4 Correct 93 ms 9432 KB Output is correct
5 Correct 3 ms 356 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 714 ms 37232 KB Output is correct
8 Correct 323 ms 37372 KB Output is correct
9 Correct 701 ms 37108 KB Output is correct
10 Correct 306 ms 37072 KB Output is correct
11 Correct 165 ms 35640 KB Output is correct
12 Correct 275 ms 35984 KB Output is correct
13 Correct 55 ms 9436 KB Output is correct
14 Correct 93 ms 9408 KB Output is correct
15 Correct 60 ms 9488 KB Output is correct
16 Correct 101 ms 9540 KB Output is correct
17 Correct 59 ms 9560 KB Output is correct
18 Correct 13 ms 9336 KB Output is correct
19 Correct 179 ms 8968 KB Output is correct
20 Correct 264 ms 36300 KB Output is correct
21 Correct 555 ms 36872 KB Output is correct
22 Correct 306 ms 36704 KB Output is correct
23 Correct 561 ms 36664 KB Output is correct
24 Correct 286 ms 36484 KB Output is correct