Submission #532617

#	Time	Username	Problem	Language	Result	Execution time	Memory
532617		cig32	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1090 ms	4196 KiB

tournament

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

const int MAXN = 1e5 + 10;
int st[17][MAXN];
int query(int l, int r) {
  int k = 32 - __builtin_clz(r-l+1) - 1; return max(st[k][l], st[k][r - (1<<k) + 1]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int dsu[N];
  for(int i=0; i<N; i++) dsu[i] = i;
  for(int i=0; i<C; i++) {
    int lb = 0, rb = N - 1;
    while(lb < rb) {
      int mid = (lb + rb) >> 1;
      if(dsu[mid] >= S[i]) rb = mid;
      else lb = mid + 1;
    }
    int lb2 = 0, rb2 = N - 1;
    while(lb2 < rb2) {
      int mid = (lb2 + rb2 + 1) >> 1;
      if(dsu[mid] <= E[i]) lb2 = mid;
      else rb2 = mid - 1;
    }
    for(int j=lb + 1; j<=lb2; j++) dsu[j] = dsu[lb];
    for(int j=lb2 + 1; j<N; j++) dsu[j] -= (E[i] - S[i]);
    S[i] = lb, E[i] = lb2;
  }
  /*
  for(int i=0; i<C; i++) {
    cout << "Range #" << i <<": " << S[i] << " " << E[i] << "\n";
  }
  */
  int opt_cnt = 0, opt_id = 0;
  int d[N + 1];
  for(int i=0; i<N + 1; i++) d[i] = 0;
  for(int i=0; i<N-1; i++) st[0][i] = K[i];
  for(int i=1; i<17; i++) {
    for(int j=0; j<N-1 && j + (1<<i) - 1 < N - 1; j++) {
      st[i][j] = max(st[i-1][j], st[i-1][j+(1<<(i-1))]);
    }
  }
  for(int i=0; i<C; i++) {
    if(query(S[i], E[i] - 1) < R) {
      d[S[i]]++;
      d[E[i] + 1]--;
    }
  }
  int cur = 0;
  for(int i=0; i<N; i++) {
    cur += d[i];
    if(cur > opt_cnt) {
      opt_cnt = cur, opt_id = i;
    }
  }
  return opt_id;
}

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