結果

問題 No.3640 Babies don't like Bat Beat
コンテスト
ユーザー tnakao0123
提出日時 2026-08-26 12:46:26
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 231 ms / 2,000 ms
+ 478µs
コード長 1,171 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 256 ms
コンパイル使用メモリ 57,772 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2026-08-26 12:46:42
合計ジャッジ時間 4,315 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 %
小課題1 10 % AC * 5
小課題2 10 % AC * 10
小課題3 15 % AC * 5
小課題4 20 % AC * 10
小課題5 20 % AC * 15
小課題6 25 % AC * 33
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3640.cc:  No.3640 Babies don't like Bat Beat - yukicoder
 */

#include<cstdio>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 200000;
const int BN = 30;
const int MAX_M = MAX_N * BN;

/* typedef */

/* global variables */

int ls[MAX_N], rs[MAX_N];
int uxs[MAX_M], cs[MAX_M + 1];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d%d", ls + i, rs + i);

  int maxr = *max_element(rs, rs + n);
  
  int m = 0;
  for (int i = 0; i < n; i++) {
    int l = ls[i], r = rs[i];
    while (l < maxr) {
      uxs[m++] = l, uxs[m++] = min(maxr, r);
      l <<= 1, r <<= 1;
    }
  }
  sort(uxs, uxs + m);
  m = unique(uxs, uxs + m) - uxs;
  //printf(" m=%d\n", m);

  for (int i = 0; i < n; i++) {
    int l = ls[i], r = rs[i];
    while (l < maxr) {
      int li = lower_bound(uxs, uxs + m, l) - uxs;
      int ri = lower_bound(uxs, uxs + m, min(maxr, r)) - uxs;
      cs[li]++, cs[ri]--;
      l <<= 1, r <<= 1;
    }
  }

  for (int i = 0; i < m; i++) cs[i + 1] += cs[i];
  int maxc = *max_element(cs, cs + m);
  
  printf("%d\n", maxc);
  
  return 0;
}
0