제출 #1185114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185114		peteza	마상시합 토너먼트 (IOI12_tournament)	C++20	0 / 100	7 ms	15940 KiB

tournament

#include <cstring>
#include <iostream>
#include <utility>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
int sparsetable[100005][20];
int par[200005][20];
int crealnode[200005];
int segm[400005];
int cnode, csz;
std::pair<int, int> segs[300005];

void upd(int idx, int l, int r, int tgt, int val) {
  if(l == r) {segm[idx] = val; return;}
  int mid = (l + r) >> 1;
  if(tgt <= mid) upd(idx*2+1, l, mid, tgt, val);
  else upd(idx*2+2, mid+1, r, tgt, val);
  segm[idx] = segm[idx*2+1] + segm[idx*2+2];
}

int qr(int idx, int l, int r, int getpos) {
  if(!getpos) return l;
  if(l == r) return l;
  int mid = (l+r) >> 1;
  if(segm[idx*2+1] < getpos) return qr(idx*2+2, mid+1, r, getpos - segm[idx*2+1]);
  return qr(idx*2+1, l, mid, getpos);
}

int getmx(int l, int r) {
  int lg2pls = 31 - __builtin_clz(r-l+1);
  return max(sparsetable[l][lg2pls], sparsetable[r-(1<<lg2pls)+1][lg2pls]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int cmx = 0, cpos = 0;
  for(int i=0;i<N-1;i++) {
    sparsetable[i][0] = K[i];
  }
  for(int ck=1;ck<20;ck++)
    for(int i=0;i<N-1;i++)
      if(i + (1<<(ck-1)) < N-1)
        sparsetable[i][ck] = max(sparsetable[i][ck-1], sparsetable[i+(1<<(ck-1))][ck-1]);
  cnode = N;
  memset(par, -1, sizeof par);
  for(int i=0;i<N;i++) {crealnode[i] = i; segs[i] = {i, i}; upd(0, 0, N-1, i, 1);}
  for(int i=0;i<C;i++) {
    segs[cnode] = {N+9, -9};
    for(int cidx = E[i]; cidx > S[i]; cidx--) {
      int res = qr(0, 0, N-1, cidx+1);
      par[crealnode[res]][0] = cnode;
      segs[cnode].first = min(segs[cnode].first, segs[crealnode[res]].first);
      segs[cnode].second = max(segs[cnode].second, segs[crealnode[res]].second);
      upd(0, 0, N-1, res, 0);
    }
    int res = qr(0, 0, N-1, S[i]+1);
    par[crealnode[res]][0] = cnode;
    segs[cnode].first = min(segs[cnode].first, segs[crealnode[res]].first);
    segs[cnode].second = max(segs[cnode].second, segs[crealnode[res]].second);
    crealnode[res] = cnode;
    cnode++;
  }
  for(int i=0;i<cnode;i++) {
    for(int ck=1;ck<20;ck++) {
      if(par[i][ck-1] == -1) break;
      par[i][ck] = par[par[i][ck-1]][ck-1];
    }
  }
  for(int i=0;i<N;i++) {
    //try inserting into i??
    int cdep = 0, cnode = i;
    for(int ck=19;ck>=0;ck--) {
      if(par[cnode][ck] == -1) continue;
      if(getmx(segs[par[cnode][ck]].first, segs[par[cnode][ck]].second-1) <= R) {
        cnode = par[cnode][ck];
        cdep += (1 << ck);
      }
    }
    //std::cout << i << " -> " << cdep << " (" << cnode << ") " << '\n';
    if(cmx < cdep) {
      cmx = cdep;
      cpos = i;
    }
  }
  return cpos;
}

/*
g++ tournament.cpp grader.cpp -o tournament
5 3 3 
1 0 2 4
1 3
0 1
0 1
*/

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