BOJ 15968 - 물병 잡기

BOJ 15968 - 물병 잡기

항상 모든 물병은 순서대로 세워지는 점을 이용한다.

따라서 시간 $t$에 어떤 물병이 어느 위치에 있는지 구할 수 있다면 이분탐색으로 어떤 물병부터 어떤 물병까지 그 범위안에 있는지를 알 수 있다.

일단 $0$번째 물병은 $d_0$ 주기로 재혁이의 바로 뒤로 이동한다.

그 시간을 $t_i$ 라고 하자. 그럼 그 다음부터는

$$ t_i=\left\lceil \dfrac{d_i}{t_{i-1}} \right\rceil \cdot t_{i-1} $$

이다.

바로 직전 물병이 움직이는 주기 $t_{i-1}$ 는 곧 그 직전 물병이 움직인 위치도 의미하기 때문에 $d_i$ 만큼 움직이기 위해 필요한 그 주기의 개수에 그 주기마다 직전 물병이 움직인 거리를 곱하면 현재 물병의 주기가 나온다.

그럼 $i$ 번째 물병이 시간 $T$에 있는 위치는 $-i+\left\lfloor \dfrac{T}{t_i} \right\rfloor \cdot t_i$ 이다.

void solve() {  
   int n, q;  
   cin >> n >> q;  
   vi d(n);  
   fv(d);  
   vi t(n);  
   t[0] = d[0];  
   for (int i = 1; i < n; i++) {  
      t[i] = (d[i] + t[i - 1] - 1) / t[i - 1] * t[i - 1];  
   }  
   auto pos_in_t = [&](int i, int time) {  
      return -(i + 1) + time / t[i] * t[i];  
   };  
  
   for (int i = 0; i < q; i++) {  
      int time, L, R;  
      cin >> time >> L >> R;  
  
      int tmp = 0;  
      if (L <= time && time <= R) tmp = 1;  
  
      int l = 0, r = n - 1, sp = -1;  
      while (l <= r) {  
         int mid = l + r >> 1;  
         if (pos_in_t(mid, time) <= R) sp = mid, r = mid - 1;  
         else l = mid + 1;  
      }  
      if (sp != -1 && pos_in_t(sp, time) >= L) {  
         l = sp, r = n - 1;  
         int ep = -1;  
         while (l <= r) {  
            int mid = l + r >> 1;  
            if (pos_in_t(mid, time) >= L) ep = mid, l = mid + 1;  
            else r = mid - 1;  
         }  
         assert(~ep);  
         tmp += ep - sp + 1;  
      }  
  
      cout << tmp << endl;  
   }  
}