fork download
copy 
  1. #include <assert.h>
  2. #include<stdio.h>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. #define MAX 1000005
  7.  
  8. std::vector<int> mines[MAX];
  9. int n;
  10. int strt[MAX];  // Starting of the interval at field #i.
  11.  
  12. void cleanup() {
  13.     for (int i = 0; i <= n+1; ++i) {
  14.         mines[i].clear();
  15.         strt[i] = 0;
  16.     }
  17. }
  18.  
  19. void read() {
  20.     int m;
  21.     scanf("%d%d", &n, &m);
  22.     for(int a, b; m--; ) {
  23.         scanf("%d%d", &a, &b);
  24.         assert (a >= 1 && a <= n);
  25.         if (b < a) continue;  // There is no way we will reach field `a` before time `b`, so recording this mine is pointless.
  26.         mines[a].push_back(b);
  27.     }
  28.     for (int i = 1; i <= n; ++i)
  29.         std::sort(mines[i].rbegin(), mines[i].rend());
  30. }
  31.  
  32. int bomb(const int field, const int start, const int end) {
  33.     // Find a bomb in field #field, between `start` and `end` time.
  34.     auto& v = mines[field];
  35.     while (!v.empty() && v.back() < start) v.pop_back();
  36.     if (v.empty() || v.back() > end) {
  37.         return 0;
  38.     }
  39.     return v.back();
  40. }
  41.  
  42. int solve() {
  43.     // `pos` tracks the position you are currently on.
  44.     // `time` tracks the end of the time interval you must spend at the current position (tracked by `pos`).
  45.     int pos = 0, time = 0;  
  46.     strt[pos] = 0;  // `strt[i]` tracks the start of the time interval you must spend at position `i`.
  47.     while (pos < n + 1) {
  48.         const int b = bomb(pos, strt[pos], time);
  49.         if (b) {
  50.             // There is a bomb in this field during this range. It detonates at time `b`.
  51.             // Take one step back, and make sure to stay there until time `b`.
  52.             pos = pos - 1;
  53.             time = b;
  54.         } else {
  55.             // No bomb in this field during the interval you intend to spend here.
  56.             // Advance one step, and increase the time by 1.
  57.             pos = pos + 1;
  58.             time = time + 1;
  59.             assert(strt[pos] < time);
  60.             strt[pos] = time;
  61.         }
  62.     }
  63.     return time;
  64. }
  65.  
  66. int main() {
  67.     int TC;
  68.     scanf("%d",&TC);
  69.     while(TC--) {
  70.         read();
  71.         printf("%d\n", solve());
  72.         cleanup();
  73.     }
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 28200KB
comments (?)
stdin
copy 
2
3 3
1 0
2 1
1 2
4 4
1 3
2 2
3 1
4 2
stdout
copy 
4
6
https://ideone.com/KiqMxR
language:
C++14 (gcc 8.3)
created:
333 days ago
visibility:
secret

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!