Submission #1171750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171750		fryingduc	Floppy (RMI20_floppy)	C++20	100 / 100	65 ms	7616 KiB

floppy

#include <stdlib.h>
#include <string.h>

#include "floppy.h"
#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif

const int maxn = 4e4 + 4;
const int LG = 15;
int n, st[maxn][LG + 1];
string send;
vector<int> vl;

void calc(int l, int r) {
  if (l > r) return;
  auto get = [&](int l, int r) {
    int p = 31 - __builtin_clz(r - l + 1);
    return vl[st[l][p]] > vl[st[r - (1 << p) + 1][p]] ? st[l][p] : st[r - (1 << p) + 1][p];
  };
  int mid = get(l, r);
  if (l <= mid - 1) {
    send += '1';
    calc(l, mid - 1);
  } else {
    send += '0';
  }
  if (mid + 1 <= r) {
    send += '1';
    calc(mid + 1, r);
  } else {
    send += '0';
  }
}

void read_array(int subtask_id, const vector<int> &_v) {
  vl = _v;
  n = (int)vl.size();
  vl.insert(vl.begin(), 0);
  for (int i = 1; i <= n; ++i) {
    st[i][0] = i;
  }
  send = "";
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i + (1 << j) <= n + 1; ++i) {
      if (vl[st[i][j - 1]] > vl[st[i + (1 << (j - 1))][j - 1]]) {
        st[i][j] = st[i][j - 1];
      } else {
        st[i][j] = st[i + (1 << (j - 1))][j - 1];
      }
    }
  }
  calc(1, n);
  save_to_floppy(send);
}

int up[maxn][LG + 1];
int child[maxn][2];
int h[maxn];
int num_nodes;
int id;
int rv[maxn];
int tin[maxn];
int sz[maxn];

void build(int u) {
  sz[u] = 1;
  for (int ite = 0; ite < 2; ++ite) {
    if (send[id] == '1') {
      ++num_nodes;
      ++id;
      int v = num_nodes;
      child[u][ite] = v;
      h[v] = h[u] + 1;
      up[v][0] = u;
      for (int i = 1; i <= LG; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
      }
      build(v);
      sz[u] += sz[v];
    } else ++id;
  }
}

void construct(int u, int bl, int br) {
  int p = bl;
  if (child[u][0]) {
    p = sz[child[u][0]] + bl;
  }
  tin[p] = u, rv[u] = p;
  if (child[u][0]) {
    construct(child[u][0], bl, p - 1);
  }
  if (child[u][1]) {
    construct(child[u][1], p + 1, br);
  }
}

int lca(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  for (int i = LG; i >= 0; --i) {
    if ((h[u] - h[v]) >> i & 1) {
      u = up[u][i];
    }
  }
  if (u == v) return u;
  for (int i = LG; i >= 0; --i) {
    if (up[u][i] != up[v][i]) {
      u = up[u][i], v = up[v][i];
    }
  }
  return up[v][0];
}

vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
  send = bits;
  debug(send);
  n = N;
  for (int i = 1; i <= n; ++i) {
    h[i] = 0;
  }
  num_nodes = id = 0;
  build(++num_nodes);
  construct(1, 1, n);
  vector<int> res;
  for (int i = 0; i < (int)a.size(); ++i) { 
    res.push_back(rv[lca(tin[a[i] + 1], tin[b[i] + 1])] - 1);
  }
  return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72