제출 #1156008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156008		julia_08	Jousting tournament (IOI12_tournament)	C++20	100 / 100	99 ms	26184 KiB

tournament

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

const int MAXN = 2e5 + 10;

int s[MAXN], e[MAXN];

int seg[4 * MAXN], sum[MAXN];

int l[MAXN], r[MAXN], good[MAXN];

int dp[20][MAXN];

int n, c;

void build(int x, int lx, int rx){

  if(lx == rx){
    seg[x] = 1;
    return;
  }

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  build(lc, lx, m);
  build(rc, m + 1, rx);

  seg[x] = seg[lc] + seg[rc];
}

void update(int x, int lx, int rx, int l, int r){

  if(rx < l || lx > r) return;

  if(l <= lx && rx <= r){
    seg[x] = 0;
    return;
  }

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  update(lc, lx, m, l, r);
  update(rc, m + 1, rx, l, r);

  seg[x] = seg[lc] + seg[rc];
}

int bs(int x, int lx, int rx, int val){

  if(lx == rx) return lx;

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  if(seg[lc] >= val) return bs(lc, lx, m, val);

  return bs(rc, m + 1, rx, val - seg[lc]);
}

int solve(int i){
  // quanto eu consigo subir na árvore a partir da pos i

  int r = 0;

  for(int k=19; k>=0; k--){
    if(good[dp[k][i]]){
      i = dp[k][i];
      r += (1 << k);
    }
  }

  return r;
}

int GetBestPosition(int n_, int c_, int rnk, int *k, int *s_, int *e_){

  n = n_, c = c_;

  // indexando tudo para 1
  for(int i=n; i>=1; i--) k[i] = (k[i - 1] <= rnk ? 0 : 1);
  for(int i=c; i>=1; i--) s[i] = s_[i - 1] + 1, e[i] = e_[i - 1] + 1;

  build(1, 1, n + 1);

  for(int i=1; i<=n; i++){
    l[i] = r[i] = i; // folhas
    sum[i] = sum[i - 1] + k[i];
  }

  set<pair<int, int>> active;

  for(int i=1; i<=n; i++) active.insert({i, i});

  int cur = n;

  for(int i=1; i<=c; i++){

    int sz = e[i] - s[i] + 1; // quantos caras quero tirar

    s[i] = bs(1, 1, n + 1, s[i]); // s[i] = primeiro cara que tem cnt_ativos >= s[i]
    e[i] = bs(1, 1, n + 1, e[i] + 1) - 1; // (e[i] = primeiro cara que tem cnt_ativos > e[i]) - 1

    update(1, 1, n + 1, s[i] + 1, e[i]); // suponho que o primeiro cara ganhou

    cur ++;

    l[cur] = s[i], r[cur] = e[i]; // folha de menor e maior indice

    vector<pair<int, int>> to_erase;

    auto it = active.lower_bound({s[i], 0});

    while((int) to_erase.size() < sz){
      to_erase.push_back(*it);
      it ++;
    }

    for(auto [x, i] : to_erase){
      active.erase({x, i});
      dp[0][i] = cur; // cur é pai de i
    }

    active.insert({s[i], cur});

  }

  /*for(int i=1; i<=n+c; i++){
    cout << i << " pai[" << i << "] = " << dp[0][i] << ", l[" << i << "] = " << l[i] << " and r[" << i << "] = " << r[i] << "\n";
  }*/

  // binary-lifting

  dp[0][n + c] = 0;

  for(int i=1; i<=n+c; i++){
    good[i] = (sum[r[i] - 1] - sum[l[i] - 1] == 0);
  }

  for(int k=1; k<20; k++){
    for(int i=1; i<=n+c; i++){
      dp[k][i] = dp[k - 1][dp[k - 1][i]];
    }
  }

  pair<int, int> ans = {-1, 1e9};

  for(int i=1; i<=n; i++){

    // cout << i << " " << solve(i) << "\n";

    int cur_ans = solve(i);

    if(cur_ans > ans.first){
      ans = {cur_ans, i};

    } else if(cur_ans == ans.first){
      ans.second = min(ans.second, i);
    }

  }

  return ans.second - 1;
}

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