CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) - D. Climbing the Tree (1700)

D. Climbing the Tree

계속 가능한 구간 $[L, R]$ 을 관리한다.

$2$번 쿼리는 달팽이가 $a,b,h$ 를 가졌을 때 걸리는 시간을 구하는 함수인

int days(int a, int b, int h) {  
   if (h <= a) return 1;  
   h -= a;  
   return 1 + (h + (a - b) - 1) / (a - b);  
}

를 짠다음에

$days(a,b,L)=days(a,b,R)$ 인지를 검사하면 된다.

$1$ 번 쿼리에 대해 생각해보자.

$n=1$ 일때는 $h$가 가장작으려면 $h=1$, 가장 크려면 $h=a$ 여야 한다.

$n=2$ 일때는

$h$가 가장 작으려면 $n-1$ 일에 $a$를 쭉 올라갔는데 닿지 못하고 그 다음날 바로 올라갔어야 하므로

$h-1=(a-b)(n-2)+a$ 여야 학,

$h$가 가장 크려면 $n$ 일째에 $a$를 쭉올라가서 바로 $h$에 닿고 $n-1$ 일들은 $a-b$ 만큼 올라간 것이여야 하므로

$h=a+(a-b)(n-1)$ 이여야 한다.

이 수식들로 쿼리를 적절히 처리해줄 수 있다.

int days(int a, int b, int h) {  
   if (h <= a) return 1;  
   h -= a;  
   return 1 + (h + (a - b) - 1) / (a - b);  
}  
void solve() {  
   int n;  
   cin >> n;  
   int l = -1, r = -1;  
   for (int i = 0; i < n; i++) {  
      int t, a, b, n;  
      cin >> t;  
      if (t == 1) {  
         cin >> a >> b >> n;  
         int low, high;  
         if (n == 1) {  
            low = 1;  
            high = a;  
         } else {  
            high = a + (a - b) * (n - 1);  
            low = a + (a - b) * (n - 2) + 1;  
         }  
         assert(low <= high);  
         if (l == -1) {  
            l = low, r = high;  
            cout << 1 << ' ';  
         } else {  
            if (low > r || high < l) {  
               cout << 0 << ' ';  
            } else {  
               maxa(l, low);  
               mina(r, high);  
               cout << 1 << ' ';  
            }  
         }  
      } else {  
         cin >> a >> b;  
         if (l == -1) {  
            cout << -1 << ' ';  
         } else {  
            int low = days(a, b, l);  
            int high = days(a, b, r);  
            if (low == high) cout << low << ' ';  
            else cout << -1 << ' ';  
         }  
      }  
   }  
   cout << endl;  
}