Submission #373415

#	Time	Username	Problem	Language	Result	Execution time	Memory
373415		WLZ	Jousting tournament (IOI12_tournament)	C++14	0 / 100	88 ms	8940 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 + 1);
      }
    }

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

    int find(int x) {
      int lo = 0, hi = n - 1;
      while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (query(mid) <= x) lo = mid;
        else hi = mid - 1;
      }
      return lo;
    }
};

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(0, n - 1, 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, N);
  vector<int> pre(N + 2, 0);
  for (int i = 0; i < C; i++) {
    int l = fenw.find(S[i]) + 1, r = fenw.find(E[i] + 1);
    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 - 1, r - 2) <= 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: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51