fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. int n, q, blockSize;
  7. vector<int> jump;           // jump power at each position
  8. vector<int> nextOut;        // next position that jumps out of the block from i
  9. vector<int> jumpCount;      // number of small steps to reach nextOut[i]
  10.  
  11. // Rebuild the block containing startIndex
  12. void rebuildBlock(int startIndex) {
  13.     // 1-indexed
  14.     int id = (startIndex - 1) / blockSize;
  15.     int leftBound = id * blockSize + 1;
  16.  
  17.     for (int i = startIndex; i >= leftBound; --i) {
  18.         int target = i + jump[i];
  19.  
  20.         // If jumps out of the array or to a different block
  21.         if (target > n || (target - 1) / blockSize != (i - 1) / blockSize) {
  22.             nextOut[i] = target;
  23.             jumpCount[i] = 1;
  24.         }
  25.         // If still in the same block
  26.         else {
  27.             nextOut[i] = nextOut[target];
  28.             jumpCount[i] = jumpCount[target] + 1;
  29.         }
  30.     }
  31. }
  32.  
  33. int main() {
  34.     ios::sync_with_stdio(false);
  35.     cin.tie(nullptr);
  36.  
  37.     cin >> n >> q;
  38.  
  39.     // Calculate block size
  40.     blockSize = max(1, (int)sqrt(n));
  41.  
  42.     jump.assign(n + 2, 0);
  43.     nextOut.assign(n + 2, 0);
  44.     jumpCount.assign(n + 2, 0);
  45.  
  46.     for (int i = 1; i <= n; ++i) cin >> jump[i];
  47.  
  48.     // PREPROCESSING: build nextOut and jumpCount
  49.     for (int i = n; i >= 1; --i) {
  50.         int target = i + jump[i];
  51.  
  52.         if (target > n || (target - 1) / blockSize != (i - 1) / blockSize) {
  53.             nextOut[i] = target;
  54.             jumpCount[i] = 1;
  55.         } else {
  56.             nextOut[i] = nextOut[target];
  57.             jumpCount[i] = jumpCount[target] + 1;
  58.         }
  59.     }
  60.  
  61.     // PROCESS QUERIES
  62.     while (q--) {
  63.         int type;
  64.         cin >> type;
  65.  
  66.         // UPDATE: jump[pos] = val
  67.         if (type == 0) {
  68.             int pos, val;
  69.             cin >> pos >> val;
  70.             jump[pos] = val;
  71.  
  72.             rebuildBlock(pos);  // Rebuild the block containing pos
  73.         }
  74.  
  75.         else {
  76.             // QUERY: output final position + number of steps
  77.             int curPos;
  78.             cin >> curPos;
  79.  
  80.             int totalSteps = 0;
  81.  
  82.             // Jump by blocks first
  83.             while (curPos <= n && nextOut[curPos] <= n) {
  84.                 totalSteps += jumpCount[curPos];
  85.                 curPos = nextOut[curPos];
  86.             }
  87.  
  88.             // Jump by individual steps when outside the block
  89.             while (curPos + jump[curPos] <= n) {
  90.                 curPos += jump[curPos];
  91.                 totalSteps++;
  92.             }
  93.  
  94.             totalSteps++; // final step jumps out of the array
  95.  
  96.             cout << curPos << " " << totalSteps << "\n";
  97.         }
  98.     }
  99.  
  100.     return 0;
  101. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2
stdout 
8 7
8 5
7 3
https://ideone.com/cD2UlO
language:
C++ (gcc 8.3)
created:
2 days 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!