Submission #1098789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098789		gustavo_d	Jousting tournament (IOI12_tournament)	C++17	100 / 100	311 ms	30148 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define sc second

struct Node {
  int on, rng_idx;
  Node(int _on=0, int _rng_idx=-1):
    on(_on), rng_idx(_rng_idx) {}

  Node operator+(Node right) {
    Node left = *this;
    return Node(left.on + right.on);
  }
};

struct SEG {
  vector<Node> seg; int n;
  SEG(int _n) {
    n = 1;
    while (n < _n) n <<= 1;
    seg = vector<Node>(2*n);

    for (int i=0; i<_n; i++) {
      seg[n+i] = Node(1, i);
    }
    for (int i=n-1; i>=0; i--) {
      seg[i] = seg[2*i] + seg[2*i+1];
    }
  }

  int bb(int v, int l, int r, int k) {
    // acha idx do k-ésimo ativo
    if (l == r) {
      return l;
    }
    int m = (l + r) / 2;
    if (seg[2*v].on >= k)
      return bb(2*v, l, m, k);
    else return bb(2*v+1, m+1, r, k - seg[2*v].on);
  }

  void turn_off(int v, int l, int r, int i) {
    // desativa posição i
    if (l == r) {
      seg[v].on = 0;
      return;
    }

    int m = (l + r) / 2;
    if (i <= m) turn_off(2*v, l, m, i);
    else turn_off(2*v+1, m+1, r, i);
    seg[v] = seg[2*v] + seg[2*v+1];
  }
};

const int MAXN = 2e5; // nós nó grafo
const int MAXLOG = 25;

int f[MAXLOG+1][MAXN];
vector<pair<int,int>> rngs;

struct NodeMax {
  int mx;
  NodeMax(int _mx=-1e9): mx(_mx) {}

  NodeMax operator+(NodeMax right) {
    NodeMax left = *this;
    return NodeMax(max(left.mx, right.mx));
  }
};

struct SEGMax {
  vector<NodeMax> seg; int n;
  SEGMax(int _n) {
    n = 1;
    while (n < _n) n <<= 1;
    seg = vector<NodeMax> (2*n);
  }

  void update(int v, int l, int r, int i, int val) {
    if (l == r) {
      seg[v].mx = val;
      return;
    }

    int m = (l + r) / 2;
    if (i <= m) update(2*v, l, m, i, val);
    else update(2*v+1, m+1, r, i, val);
    seg[v] = seg[2*v] + seg[2*v+1];
  }

  NodeMax mx(int v, int l, int r, int a, int b) {
    // contido
    if (a <= l and r <= b) return seg[v];
    // fora
    if (r < a or l > b) return NodeMax();
    // parcialmente
    int m = (l + r) / 2;
    return mx(2*v, l, m, a, b) + mx(2*v+1, m+1, r, a, b);
  }
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  // lê input
  int n = N;
  int qs = C; // rounds
  int late = R;
  vector<int> pos(n-1);
  for (int i=0; i<n-1; i++) pos[i] = K[i];
  pair<int,int> rounds[qs];
  for (int i=0; i<qs; i++) {
    rounds[i] = {S[i]+1, E[i]+1};
  }


  // gera ranges e relação entre eles
  for (int i=0; i<n; i++) {
    rngs.emplace_back(i, i);
  }
  SEG seg(n);

  for (int i=0; i<qs; i++) {
    // cout << "round" << rounds[i].fi << ' ' << rounds[i].sc << '\n';
    vector<int> nodes;
    for (int j=rounds[i].fi; j<=rounds[i].sc; j++) {
      // cout << j << '(' << seg.bb(1, 0, seg.n-1, j) << ')';
      nodes.push_back(seg.bb(1, 0, seg.n-1, j));
      // cout << ' ';
    }
    // cout << endl;

    // aponta ranges pro novo
    int new_rng_idx = (int)rngs.size();
    for (int node : nodes) {
      int rng_idx = seg.seg[seg.n + node].rng_idx;
      f[0][rng_idx] = new_rng_idx;
    }

    // novo range na posição do primeiro usado
    int l = rngs[seg.seg[seg.n + nodes[0]].rng_idx].fi;
    int r = rngs[seg.seg[seg.n + nodes.back()].rng_idx].sc;
    rngs.emplace_back(l, r);
    seg.seg[seg.n + nodes[0]].rng_idx = new_rng_idx;

    // desativa demais
    for (int j=1; j<(int)nodes.size(); j++) {
      seg.turn_off(1, 0, seg.n-1, nodes[j]);
    }
  }


  // binary lifting da árvore gerada
  int qty_rngs = (int)rngs.size();
  f[0][qty_rngs-1] = -1;
  // for (int i=0; i<qty_rngs; i++) {
  //   // cout << rngs[i].fi << ' ' << rngs[i].sc << " cujo pai " << f[0][i] << endl;
  // }
  for (int b=1; b<=MAXLOG; b++) {
    for (int i=0; i<qty_rngs; i++) {
      if (f[b-1][i] == -1) {
        f[b][i] = -1;
        continue;
      }
      f[b][i] = f[b-1][f[b-1][i]];
    }
  }


  // testa colocações do r
  pair<int, int> ans = {-1, 0};
  SEGMax segmx(2*n-1);
  for (int i=1; i<2*n-1; i+=2) {
    segmx.update(1, 0, segmx.n-1, i, pos[i/2]);
  }
  for (int i=0, pos=1; pos<=n; pos++, i+=2) {
    segmx.update(1, 0, segmx.n-1, i, late);

    int v = pos-1; // começa neste range
    int tmp_ans = 0;
    for (int b=MAXLOG; b>=0; b--) {
      if (f[b][v] == -1) continue;

      // cout << "check" << (1 << b) << endl;
      // ganha dentro do range f[b][v]?
      pair<int,int> rng = rngs[f[b][v]];
      rng.fi++; rng.sc++;
      // cout << rng.first << ' ' << rng.second << endl;
      int li = i;
      int delta_l = pos - rng.fi;
      if (delta_l > 0) {
        delta_l--;
        li--;
      }
      li -= 2*delta_l;
      int ri = i;
      int delta_r = rng.sc - pos;
      if (delta_r > 0) {
        delta_r--;
        ri++;
      }
      ri += 2*delta_r;
      // cout << "range na SEG" << li << ' ' << ri << endl;
      int mx = segmx.mx(1, 0, segmx.n-1, li, ri).mx;
      // cout << "max" << mx << endl;

      if (mx == late) { // ganha
        v = f[b][v];
        tmp_ans += (1 << b);
      }
    }

    // cout << tmp_ans << endl;
    if (tmp_ans > ans.first) {
      ans = {tmp_ans, pos-1};
    }
    segmx.update(1, 0, segmx.n-1, i, -1e9);
  }


  return ans.second;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51