Submission #685141

#	Time	Username	Problem	Language	Result	Execution time	Memory
685141		tvladm2009	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	714 ms	37372 KiB

weirdtree

#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 (stderr)

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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29