oj.uz

Submission #373434

# Submission time Handle Problem Language Result Execution time Memory
373434 2021-03-04T14:54:27 Z WLZ Jousting tournament (IOI12_tournament) C++14
100 / 100
 148 ms 18156 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 6 ms 1132 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 8 ms 1152 KB Output is correct
5 Correct 6 ms 1132 KB Output is correct
6 Correct 6 ms 1132 KB Output is correct
7 Correct 7 ms 1132 KB Output is correct
8 Correct 6 ms 1132 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 7 ms 1132 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 8812 KB Output is correct
2 Correct 133 ms 18048 KB Output is correct
3 Correct 57 ms 16364 KB Output is correct
4 Correct 125 ms 18156 KB Output is correct
5 Correct 121 ms 17260 KB Output is correct
6 Correct 148 ms 17304 KB Output is correct
7 Correct 129 ms 18156 KB Output is correct
8 Correct 132 ms 18156 KB Output is correct
9 Correct 67 ms 16108 KB Output is correct
10 Correct 64 ms 16236 KB Output is correct