Submission #1164062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164062		HappyCapybara	Jousting tournament (IOI12_tournament)	C++20	0 / 100	1 ms	328 KiB

tournament

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

bool mx = false;
int n;
vector<int> st;
vector<vector<int>> p;
vector<int> l, r;

void update(int pos, int val, int node=1, int tl=0, int tr=n-1){
  if (tl == tr){
    st[node] = val;
    return;
  }
  int tm = (tl+tr)/2;
  if (pos <= tm) update(pos, val, node*2, tl, tm);
  else update(pos, val, node*2+1, tm+1, tr);
  if (!mx) st[node] = st[node*2]+st[node*2+1];
  else st[node] = max(st[node], st[node*2]);
}

int query(int l, int r, int node=1, int tl=0, int tr=n-1){
  if (l > r) return 0;
  if (l <= tl && tr <= r) return st[node];
  int tm = (tl+tr)/2;
  int res = 0;
  if (l <= tm){
    if (!mx) res += query(l, r, node*2, tl, tm);
    else res = max(res, query(l, r, node*2, tl, tm));
  }
  if (tm+1 <= r){
    if (!mx) res += query(l, r, node*2+1, tm+1, tr);
    else res = max(res, query(l, r, node*2+1, tm+1, tr));
  }
  return res;
}

int idx(int s){
  int node = 1, tl=0, tr=n-1;
  while (tl != tr){
    if (st[node*2] >= s){
      node = node*2;
      tr = (tl+tr)/2;
    }
    else {
      s -= st[node*2];
      node = node*2+1;
      tl = (tl+tr)/2 + 1;
    }
  }
  return tl;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
  n = N;
  p.resize(N+C, vector<int>(20));
  st.resize(4*N, 0);
  for (int i=0; i<N; i++) update(i, 1);
  map<int,int> m;
  for (int i=0; i<N; i++) m[i] = i;
  for (int i=0; i<C; i++){
    //cout << i << endl;
    int s = idx(S[i]+1), e = idx(E[i]+1);
    //cout << s << " " << e << endl;
    auto it = m.find(s);
    while (true){
      //cout << "x" << endl;
      p[it->second][0] = N+i;
      update(it->first, 0);
      auto bruh = it;
      bool stop = false;
      if (it->first == e) stop = true;
      it++;
      m.erase(bruh);
      if (stop) break;
    }
    update(s, 1);
    m[s] = N+i;
  }
  p[N+C-1][0] = N+C-1;
  //for (int i=0; i<N+C; i++) cout << p[i][0] << endl;
  //cout << "d" << endl;
  for (int j=1; j<20; j++){
    for (int i=0; i<N+C; i++) p[i][j] = p[p[i][j-1]][j-1];
  }
  if (R == N-1){
    int bsf = 0, bo = 0;
    for (int i=0; i<N; i++){
      int cur = i, res = 0;
      for (int j=19; j>=0; j--){
        if (p[cur][j] != N+C-1){
          cur = p[cur][j];
          res += (1<<j);
        }
      }
      if (res > bsf){
        bsf = res;
        bo = i;
      }
    }
    return bo;
  }
  l.resize(C, 100000);
  r.resize(C, -1);
  for (int i=0; i<N; i++){
    l[p[i][0]-N] = min(l[p[i][0]-N], i);
    r[p[i][0]-N] = max(r[p[i][0]-N], i);
  }
  for (int i=0; i<C-1; i++){
    l[p[N+i][0]-N] = min(l[p[N+i][0]-N], l[i]);
    r[p[N+i][0]-N] = max(r[p[N+i][0]-N], r[i]);
  }
  //cout << "f" << endl;
  mx = true;
  for (int i=0; i<N-1; i++) update(i, K[i]);
  update(N-1, 0);
  int bsf = -1, bo;
  for (int i=0; i<N; i++){
    int lo=0, hi=C+1;
    while (lo != hi-1){
      int mid = (lo+hi)/2;
      int cur = i, cm = mid;
      for (int j=19; j>=0; j--){
        if (cm >= (1<<j)){
          cur = p[cur][j];
          cm -= (1<<j);
        }
      }
      if (R > query(l[cur-N], r[cur-N]-1)) lo = mid;
      else hi = mid;
    }
    if (lo > bsf){
      bsf = lo;
      bo = i;
    }
  }
  return bo;
}

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