Submission #879745

#	Time	Username	Problem	Language	Result	Execution time	Memory
879745		NeroZein	Jousting tournament (IOI12_tournament)	C++17	17 / 100	1053 ms	1880 KiB

tournament

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

const int M = 5003;

pair<int, int> seg[M * 2];

void build(int nd, int l, int r, const vector<int>& a) {
  if (l == r) {
    seg[nd].first = 1;
    seg[nd].second = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build(nd + 1, l, mid, a);
  build(rs, mid + 1, r, a); 
  seg[nd].first = seg[nd + 1].first + seg[rs].first;
  seg[nd].second = max(seg[nd + 1].second, seg[rs].second); 
}

void upd(int nd, int l, int r, int p) {
  if (l == r) {
    seg[nd].first = seg[nd].second = 0; 
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p); 
  } else {
    upd(rs, mid + 1, r, p); 
  }
  seg[nd].first = seg[nd + 1].first + seg[rs].first;
  seg[nd].second = max(seg[nd + 1].second, seg[rs].second); 
}

int getfirstpos(int nd, int l, int r, int k) {
  if (l == r) {
    return (k == seg[nd].first ? l : -1);
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  int ret = getfirstpos(nd + 1, l, mid, k);
  if (ret == -1) {
    ret = getfirstpos(rs, mid + 1, r, k - seg[nd + 1].first); 
  }
  return ret; 
}

int getmx(int nd, int l, int r, int s, int e) {
  if (l >= s && r <= e) {
    return seg[nd].second;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return getmx(nd + 1, l, mid, s, e);
  } else {
    if (mid < s) {
      return getmx(rs, mid + 1, r, s, e); 
    } else {
      return max(getmx(nd + 1, l, mid, s, e), getmx(rs, mid + 1, r, s, e)); 
    }
  }
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int ret = 0, best = 0; 
  for (int i = 0; i < N; ++i) {
    int pos = i, tmp = 0; 
    vector<int> a(N);
    a[pos] = R; 
    for (int j = 0; j < pos; ++j) {
      a[j] = K[j];
    }
    for (int j = pos + 1; j < N; ++j) {
      a[j] = K[j - 1]; 
    }
    build(0, 0, N - 1, a); 
    for (int j = 0; j < C; ++j) {
      int l = S[j], r = E[j]; 
      int al = getfirstpos(0, 0, N - 1, l + 1); 
      int ar = getfirstpos(0, 0, N - 1, r + 1); 
      int mx = getmx(0, 0, N - 1, al, ar); 
      if (mx == R) {
        tmp++; 
      }
      int len = r - l + 1; 
      for (int k = al, cnt = 0, o = 0; cnt < len; cnt++) {
        if (a[k] != mx) {
          upd(0, 0, N - 1, k);  
        } else {
          o++; 
        }
        k = getfirstpos(0, 0, N - 1, l + 1 + o); 
      }
    }
    if (tmp > best) {
      ret = i; 
      best = tmp; 
    }
  }
  return ret;
}

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