Submission #373434

#	Time	Username	Problem	Language	Result	Execution time	Memory
373434		WLZ	Jousting tournament (IOI12_tournament)	C++14	100 / 100	148 ms	18156 KiB

tournament

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

class fenwick_tree {
  private: 
    int n;
    vector<int> fenw;
  public:
    fenwick_tree(int _n) : n(_n) {
      fenw.assign(n, 0);
    }

    void update(int x, int val) {
      while (x < n) {
        fenw[x] += val;
        x += x & -x;
      }
    }

    int query(int x) {
      int ans = 0;
      while (x > 0) {
        ans += fenw[x];
        x -= x & -x;
      }
      return ans;
    }

    int find(int x) {
      int pos = 0, save = x;
      for (int i = 20; i >= 0; i--) {
        if (pos + (1 << i) >= n) continue;
        if (fenw[pos + (1 << i)] < x) {
          pos += (1 << i);
          x -= fenw[pos];
        }
      }
      return pos + (save > 0);
    }
};

class segment_tree {
  private:
    struct node {
      int l, r, val;
      node *left, *right;
    } *root;

    node *build(int l, int r, int *a) {
      if (l == r) return new node{l, r, a[l], nullptr, nullptr};
      node *left = build(l, (l + r) / 2, a);
      node *right = build((l + r) / 2 + 1, r, a);
      return new node{l, r, max(left->val, right->val), left, right};
    }

    int query(int l, int r, node *cur) {
      if (cur->l > r || cur->r < l) return -1;
      if (cur->l >= l && cur->r <= r) return cur->val;
      return max(query(l, r, cur->left), query(l, r, cur->right));
    }
  public:
    segment_tree(int *a, int n) {
      root = build(1, n, a);
    }

    int query(int l, int r) {
      return query(l, r, root);
    }
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  set<int> st;
  fenwick_tree fenw(N + 1);
  for (int i = 1; i <= N; i++) {
    st.insert(i);
    fenw.update(i, +1);
  }
  segment_tree seg(K - 1, N - 1);
  vector<int> pre(N + 2, 0);
  for (int i = 0; i < C; i++) {
    S[i]++; E[i]++;
    int l = fenw.find(S[i] - 1) + 1, r = fenw.find(E[i]);
    auto it = st.lower_bound(l);
    while (next(it) != st.end() && *next(it) <= r) {
      fenw.update(*it, -1);
      it = st.erase(it);
    }
    if (seg.query(l, r - 1) <= R) {
      pre[l]++; pre[r + 1]--;
    }
  }
  int ans = 0;
  for (int i = 1; i <= N; i++) {
    pre[i] += pre[i - 1];
    if (pre[i] > pre[ans]) ans = i;
  }
  return max(ans - 1, 0);
}

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