fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     short T;
  6.     cin >> T;
  7.     for ( short i = 1 ; i < T+1 ; i++)
  8.     {
  9.         int N, K; cin >> N >> K; 
  10.         pair <int, int> intervals[N];
  11.         for (int j = 0 ; j < N ; j++){
  12.             cin >> intervals[j].first >> intervals[j].second;
  13.         }
  14.         sort(intervals, intervals + N);
  15.         int current_step = intervals[0].first + K, steps = 1;
  16.         for (int j = 0 ; j < N; j++)
  17.         {
  18.             if ( intervals[j].second <= current_step){
  19.                 continue;
  20.             }
  21.             if ( intervals[i].first < current_step)
  22.             	{
  23.                 int steps_passed = (intervals[j].second - current_step)/ K;
  24.                 steps += steps_passed;
  25.                 current_step += (steps_passed * K);
  26.                 if (current_step < intervals[j].second){
  27.                     current_step += K, steps++;
  28.                 }
  29.             } else
  30.             {
  31.                 int steps_passed = (intervals[j].second - current_step)/ K;
  32.                 steps += steps_passed;
  33.                 current_step = intervals[j].first + (steps_passed * K) ;
  34.                 if (current_step < intervals[j].second){
  35.                     current_step += K, steps++;
  36.                 }
  37.             }
  38.         }
  39.         cout << "Case #" << i << ": " << steps << '\n' ;
  40.     }
  41. }
  42.  
  43.  
Success #stdin #stdout 0s 4580KB
comments (?)
stdin
copy 
2
3 5
1 5
10 11
8 9
3 2
1 2
3 5
13 14
stdout
copy 
Case #1: 2
Case #2: 6
https://ideone.com/XsbB9E
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!