fork download
copy 
  1. // ~~ icebear love attttt ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<int, int> ii;
  6. typedef pair<int, ii> iii;
  7.  
  8. template<class T>
  9.     bool minimize(T &a, const T &b) {
  10.         if (a > b) return a = b, true;
  11.         return false;
  12.     }
  13.  
  14. template<class T>
  15.     bool maximize(T &a, const T &b) {
  16.         if (a < b) return a = b, true;
  17.         return false;
  18.     }
  19.  
  20. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  21. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  22. #define REP(i, n) for(int i=0; i<(n); ++i)
  23. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  24. #define MASK(i) (1LL << (i))
  25. #define BIT(S, i) (((S) >> (i)) & 1)
  26. #define mp make_pair
  27. #define pb push_back
  28. #define fi first
  29. #define se second
  30. #define all(x) x.begin(), x.end()
  31. #define task "icebearat"
  32.  
  33. const int MOD = 1e9 + 7;
  34. const int inf = 1e9 + 27092008;
  35. const ll INF = 1e18 + 27092008;
  36. const int N = 1e5 + 5;
  37. const int BLOCK_SIZE = 369;
  38. int n, q, t[N];
  39. int f[N], nxt[N];
  40. int L[N], R[N], B[N];
  41.  
  42. // f[block][i] : minimum operation to jump from i to block + 1
  43. // nxt[block][i] : position after jump from i to next block
  44.  
  45. void update(int i) {
  46.     if (R[B[i]] == n - 1) {
  47.         if (i + t[i] >= n) {
  48.             f[i] = 1;
  49.             nxt[i] = i;
  50.         } else {
  51.             f[i] = f[i + t[i]] + 1;
  52.             nxt[i] = nxt[i + t[i]];
  53.         }
  54.         return;
  55.     }
  56.  
  57.     if (i + t[i] > R[B[i]]) {
  58.         f[i] = 1;
  59.         nxt[i] = i + t[i];
  60.     } else {
  61.         f[i] = f[i + t[i]] + 1;
  62.         nxt[i] = nxt[i + t[i]];
  63.     }
  64. }
  65.  
  66. void init(void) {
  67.     cin >> n >> q;
  68.     REP(i, n) cin >> t[i];
  69.     REP(i, BLOCK_SIZE) {
  70.         L[i] = i * BLOCK_SIZE;
  71.         R[i] = min(n, (i + 1) * BLOCK_SIZE) - 1;
  72.     }
  73.     REP(i, n) B[i] = i / BLOCK_SIZE;
  74.     RED(i, n) update(i);
  75. }
  76.  
  77. void process(void) {
  78.     int type, pos, value;
  79.     while(q--) {
  80.         cin >> type;
  81.         if (type == 0) {
  82.             cin >> pos >> value;
  83.             pos--;
  84.             t[pos] = value;
  85.             FORR(i, pos, L[B[pos]]) update(i);
  86.         } else {
  87.             cin >> pos;
  88.             pos--;
  89.             int ans = 0, block = B[pos];
  90.             while(R[block] < n - 1) {
  91.                 ans += f[pos];
  92.                 pos = nxt[pos];
  93.                 pos++;
  94.             }
  95.             ans += f[pos];
  96.             pos = nxt[pos];
  97.             cout << pos + 1 << ' ' << ans << '\n';
  98.         }
  99.     }
  100. }
  101.  
  102. int main() {
  103.     ios_base::sync_with_stdio(0);
  104.     cin.tie(0); cout.tie(0);
  105.     if (fopen(task".inp", "r")) {
  106.         freopen(task".inp", "r", stdin);
  107.         freopen(task".out", "w", stdout);
  108.     }
  109.     int tc = 1;
  110. //    cin >> tc;
  111.     while(tc--) {
  112.         init();
  113.         process();
  114.     }
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0.01s 5616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EZ5Nmg
language:
C++14 (gcc 8.3)
created:
12 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!