Submission #753733

#	Time	Username	Problem	Language	Result	Execution time	Memory
753733		nicksms	Jousting tournament (IOI12_tournament)	C++17	100 / 100	206 ms	16144 KiB

tournament

/**
 *      Author:  Nicholas Winschel
 *      Created: 06.05.2023 14:53:52
**/

#include <bits/extc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

struct inter {
  int l=0,r=0,id=0;
  inter () = default;
  inter (int l, int r, int id) : l(l), r(r), id(id) {}
};


int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  using rope = __gnu_cxx::rope<int>;
  rope r;
  V<vi> c(N);
  V<inter> is(N);
  for (int i = 0; i < N; i++) {
    is[i]=inter(i,i,i);
    r.push_back(i);
  }
  for (int i = 0; i < C; i++) {
    int j = c.size();
    c.emplace_back();
    for (int k = S[i]; k <= E[i]; k++) {
      c[j].push_back(r[k]);
    }
    r.erase(S[i],E[i]-S[i]+1);
    r.insert(S[i],j);
    is.emplace_back(is[c[j][0]].l, is[c[j][sz(c[j])-1]].r, j);
  }
  vi ans(N+1);
  vi cl(N),cr(N);
  int cnt = 0;
  for (int i = 0; i < N-1; i++) if (K[i] > R) {
    cl[i+1]++;
    cr[i]++;
    cnt++;
  }
  for (int i = 1; i < N; i++) cl[i]+=cl[i-1];
  for (int i = N-2; i >= 0; i--) cr[i]+=cr[i+1];
  auto dfs = [&](int v, auto &&dfs) -> void {
    if (v < N) return;
    if (cl[is[v].l]+cr[is[v].r] == cnt) {
      ans[is[v].l]+=1;
      ans[is[v].r+1]-=1;
    }
    for (int i : c[v]) dfs(i, dfs);
  };
  dfs(sz(c)-1,dfs);
  for (int i = 1; i <= N; i++) ans[i] += ans[i-1];

  return max_element(ans.begin(),ans.begin()+N)-ans.begin();
}

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