#203329 (C++17) No.568 じゃんじゃん　落とす　委員会

提出ソース

結果

問題	No.568 じゃんじゃん　落とす　委員会
ユーザー	ei1333333
提出日時	2017-09-08 23:43:48
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	431 ms / 1,000 ms
コード長	7,770 bytes
コンパイル時間	2,791 ms
コンパイル使用メモリ	223,180 KB
実行使用メモリ	6,400 KB
最終ジャッジ日時	2024-11-30 11:12:41
合計ジャッジ時間	9,632 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	287 ms 6,272 KB
testcase_01	AC	291 ms 6,400 KB
testcase_02	AC	216 ms 5,248 KB
testcase_03	AC	217 ms 5,248 KB
testcase_04	AC	217 ms 5,248 KB
testcase_05	AC	57 ms 5,248 KB
testcase_06	AC	215 ms 5,248 KB
testcase_07	AC	210 ms 5,248 KB
testcase_08	AC	45 ms 5,248 KB
testcase_09	AC	57 ms 5,248 KB
testcase_10	AC	58 ms 5,248 KB
testcase_11	AC	207 ms 5,248 KB
testcase_12	AC	179 ms 6,224 KB
testcase_13	AC	384 ms 6,236 KB
testcase_14	AC	325 ms 6,212 KB
testcase_15	AC	397 ms 6,232 KB
testcase_16	AC	296 ms 6,308 KB
testcase_17	AC	178 ms 6,184 KB
testcase_18	AC	341 ms 6,180 KB
testcase_19	AC	344 ms 6,348 KB
testcase_20	AC	200 ms 6,324 KB
testcase_21	AC	431 ms 6,176 KB
testcase_22	AC	287 ms 6,272 KB
testcase_23	AC	210 ms 5,248 KB
testcase_24	AC	56 ms 5,248 KB
testcase_25	AC	56 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

struct SuccinctIndexableDictionary
{
  size_t length;
  size_t blocks;
  vector< unsigned > bit, sum;

  SuccinctIndexableDictionary()
  {
  }

  SuccinctIndexableDictionary(size_t _length)
  {
    length = _length;
    blocks = (length + 31) >> 5;
    bit.assign(blocks, 0U);
    sum.assign(blocks, 0U);
  }

  void set(int k)
  {
    bit[k >> 5] |= 1U << (k & 31);
  }

  void build()
  {
    sum[0] = 0U;
    for(int i = 1; i < blocks; i++) {
      sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
    }
  }

  bool operator[](int k) const
  {
    return (bool((bit[k >> 5] >> (k & 31)) & 1));
  }

  int rank(int k)
  {
    return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
  }

  int rank(bool val, int k)
  {
    return (val ? rank(k) : k - rank(k));
  }

  int select(bool val, int k)
  {
    if(k < 0 || rank(val, length) <= k) return (-1);
    int low = 0, high = length;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(rank(val, mid) >= k + 1) high = mid;
      else low = mid;
    }
    return (high - 1);
  }

  int select(bool val, int i, int l)
  {
    return select(val, i + rank(val, l));
  }
};

template< class T, int MAXLOG >
struct WaveletMatrix
{
  size_t length;
  SuccinctIndexableDictionary matrix[MAXLOG];
  int zs[MAXLOG];
  int buff1[MAXLOG], buff2[MAXLOG];

  void max_dfs(int d, int l, int r, int &k, T val, vector< T > &vs)
  {
    if(l >= r || !k) return;
    if(d == MAXLOG) {
      while(l++ < r && k > 0) vs.push_back(val), k--;
      return;
    }
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    max_dfs(d + 1, lc + zs[d], rc + zs[d], k, 1ULL << (MAXLOG - d - 1) | val, vs);
    max_dfs(d + 1, l - lc, r - rc, k, val, vs);
  }

  T max_dfs(int d, int l, int r, T val, T a, T b)
  {
    if(r - l <= 0 || val >= b) return -1;
    if(d == MAXLOG) return val >= a ? val : -1;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    T ret = max_dfs(d + 1, lc + zs[d], rc + zs[d], 1ULL << (MAXLOG - d - 1) | val, a, b);
    if(~ret) return ret;
    return max_dfs(d + 1, l - lc, r - rc, val, a, b);
  }

  int freq_dfs(int d, int l, int r, T val, T a, T b)
  {
    if(l == r) return 0;
    if(d == MAXLOG) return (a <= val && val < b) ? r - l : 0;
    T nv = 1ULL << (MAXLOG - d - 1) | val, nnv = ((1ULL << (MAXLOG - d - 1)) - 1) | nv;
    if(nnv < a || b <= val) return 0;
    if(a <= val && nnv < b) return r - l;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    return freq_dfs(d + 1, l - lc, r - rc, val, a, b) +
           freq_dfs(d + 1, lc + zs[d], rc + zs[d], nv, a, b);
  }

  void list_dfs(int d, int l, int r, T val, T a, T b, vector< pair< T, int>> &vs)
  {
    if(val >= b || r - l <= 0) return;
    if(d == MAXLOG) {
      if(a <= val) vs.push_back(make_pair(val, r - l));
      return;
    }
    T nv = val | (1LL << (MAXLOG - d - 1)), nnv = nv | (((1LL << (MAXLOG - d - 1)) - 1));
    if(nnv < a) return;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    list_dfs(d + 1, l - lc, r - rc, val, a, b, vs);
    list_dfs(d + 1, lc + zs[d], rc + zs[d], nv, a, b, vs);
  }


  WaveletMatrix(vector< T > data)
  {
    length = data.size();
    vector< T > l(length), r(length);
    for(int depth = 0; depth < MAXLOG; depth++) {
      matrix[depth] = SuccinctIndexableDictionary(length + 1);
      int left = 0, right = 0;
      for(int i = 0; i < length; i++) {
        bool k = (data[i] >> (MAXLOG - depth - 1)) & 1;
        if(k) r[right++] = data[i], matrix[depth].set(i);
        else l[left++] = data[i];
      }
      zs[depth] = left;
      matrix[depth].build();
      swap(l, data);
      for(int i = 0; i < right; i++) data[left + i] = r[i];
    }
  }

  T access(int k)
  {
    int ret = 0;
    bool bit;
    for(int depth = 0; depth < MAXLOG; depth++) {
      bit = matrix[depth][k];
      ret = (ret << 1) | bit;
      k = matrix[depth].rank(bit, k) + zs[depth] * bit;
    }
    return (ret);
  }

  int rank(T val, int k)
  {
    int l = 0, r = k;
    for(int depth = 0; depth < MAXLOG; depth++) {
      buff1[depth] = l, buff2[depth] = r;
      bool bit = (val >> (MAXLOG - depth - 1)) & 1;
      l = matrix[depth].rank(bit, l) + zs[depth] * bit;
      r = matrix[depth].rank(bit, r) + zs[depth] * bit;
    }
    return (r - l);
  }

  int select(T val, int kth)
  {
    rank(val, length);
    for(int depth = MAXLOG - 1; depth >= 0; depth--) {
      bool bit = (val >> (MAXLOG - depth - 1)) & 1;
      kth = matrix[depth].select(bit, kth, buff1[depth]);
      if(kth >= buff2[depth] || kth < 0) return (-1);
      kth -= buff1[depth];
    }
    return (kth);
  }

  int select(T val, int k, int l)
  {
    return (select(val, k + rank(val, l)));
  }


  int quantile(int left, int right, int kth)
  {
    if(right - left <= kth || kth < 0) return (-1);
    T ret = 0;
    for(int depth = 0; depth < MAXLOG; depth++) {
      int l = matrix[depth].rank(1, left);
      int r = matrix[depth].rank(1, right);
      if(r - l > kth) {
        left = l + zs[depth];
        right = r + zs[depth];
        ret |= 1ULL << (MAXLOG - depth - 1);
      } else {
        kth -= r - l;
        left -= l;
        right -= r;
      }
    }
    return (ret);
  }

  vector< T > topk(int l, int r, int k)
  {
    if(r - l < k) k = r - l;
    if(k < 0) return (vector< T >());
    vector< T > ret;
    max_dfs(0, l, r, k, 0, ret);
    return (ret);
  }

  vector< pair< T, int > > freq_list(int l, int r, T a, T b)
  {
    vector< pair< T, int > > ret;
    list_dfs(0, l, r, 0, a, b, ret);
    return (ret);
  }

  vector< pair< int, T > > get_rect(int l, int r, T a, T b)
  {
    vector< pair< T, int > > res = freq_list(l, r, a, b);
    vector< pair< int, T > > ret;
    for(auto &e : res) {
      for(int i = 0; i < e.second; i++) {
        ret.emplace_back(select(e.first, i, l), e.first);
      }
    }
    return (ret);
  }

  int rangefreq(int left, int right, T lower, T upper)
  {
    return (freq_dfs(0, left, right, 0, lower, upper));
  }
};


int main()
{
  int N, M, X[100000], A[100000], B[100000];

  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    scanf("%d %d %d", &X[i], &A[i], &B[i]);
  }

  vector< pair< int, int > > line[4];
  vector< WaveletMatrix< int, 22 > > matrix;
  for(int i = 0; i < 4; i++) {
    for(int j = 0; j < N; j++) {
      if(X[j] == i) line[i].emplace_back(A[j], B[j]);
    }
    sort(begin(line[i]), end(line[i]));
    vector< int > build;
    for(auto &p : line[i]) build.push_back(p.second);
    matrix.emplace_back(WaveletMatrix< int, 22 >(build));
  }

  int ret = INF;

  // あーーー尺取りかーーー（わかりひるど

  int tail = 0;

  for(int i = 0; i <= 100001; i++) {
    auto check = [&](int v)
    {
      int two = 0;
      two += matrix[0].rangefreq(lower_bound(begin(line[0]), end(line[0]), make_pair(i, -1)) - begin(line[0]), line[0].size(), v, 114514);
      two += line[1].size() - matrix[1].rangefreq(0, lower_bound(begin(line[1]), end(line[1]), make_pair(i, -1)) - begin(line[1]), 0, v);
      two += line[2].size();
      two += line[3].size();
      return (two >= M);
    };

    auto get = [&](int v)
    {
      int three = 0;
      three += matrix[1].rangefreq(lower_bound(begin(line[1]), end(line[1]), make_pair(i, -1)) - begin(line[1]), line[1].size(), v, 114514);
      three += line[2].size() - matrix[2].rangefreq(0, lower_bound(begin(line[2]), end(line[2]), make_pair(i, -1)) - begin(line[2]), 0, v);
      three += line[3].size();
      return (three);
    };

    while(tail - 1 >= 0 && !check(tail)) --tail;
    while(tail + 1 <= 100001 && check(tail + 1)) ++tail;
    if(check(tail)) ret = min(ret, get(tail));
  }

  printf("%d\n", ret);
}

yukicoder

結果

テストケース

ソースコード