Submission #3007801


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

struct M {
  using T = int;
  static T op(const T& a, const T& b) { return a + b; }
  static constexpr T e() { return 0; }
};

template<class M> struct ST {
  using T = typename M::T;
  int n;
  V<T> t;

  ST(int n) : n(n) {
    t.assign(2 * n, M::e());
  }

  void build() {
    for (int i = n - 1; i; i--) t[i] = M::op(t[2 * i], t[2 * i + 1]);
  }

  T get(int l, int r) {
    T resl = M::e(), resr = M::e();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) { 
      if (l & 1) resl = M::op(resl, t[l++]); 
      if (r & 1) resr = M::op(t[--r], resr);
    }
    return M::op(resl, resr);
  }

  void set(int i, const T& a) {
    for (t[i += n] = a; i >>= 1;) t[i] = M::op(t[2 * i], t[2 * i + 1]);
  }
};

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, k; cin >> n >> k;
  V<> x(n); for (int i = 0; i < n; i++) cin >> x[i], x[i]--;
  V<> ix(n); for (int i = 0; i < n; i++) ix[x[i]] = i;
  ST<M> st(n);
  for (int i = 0; i < n; i++) {
    st.set(x[i], 1);
    if (i < k - 1) continue;
    int l = 0, r = n;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (st.get(0, m) < k) l = m;
      else r = m;
    }
    cout << ix[r - 1] + 1 << '\n';
  }
}

Submission Info

Submission Time
Task B - 特別賞
User risujiroh
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1613 Byte
Status AC
Exec Time 49 ms
Memory 2304 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 40 / 40 60 / 60
Status
AC × 2
AC × 13
AC × 22
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask2_01.txt AC 7 ms 512 KB
subtask2_02.txt AC 1 ms 256 KB
subtask2_03.txt AC 48 ms 2176 KB
subtask2_04.txt AC 45 ms 2304 KB
subtask2_05.txt AC 13 ms 1792 KB
subtask2_06.txt AC 37 ms 2176 KB
subtask2_07.txt AC 47 ms 2176 KB
subtask2_08.txt AC 44 ms 2176 KB
subtask2_09.txt AC 49 ms 2176 KB