fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FILE "SHIP"
  4.  
  5. #define int long long
  6. #define ii pair<int, int>
  7. #define iii pair<int, ii>
  8.  
  9. #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  10. #define FOR(I, L, R) for(int I = (int)L; I <= (int)R; I++)
  11. #define FOD(I, R, L) for(int I = (int)R; I >= (int)L; I--)
  12. #define FOA(I, A) for(auto &I : A)
  13.  
  14. #define all(A) A.begin(), A.end()
  15. #define fi first
  16. #define se second
  17.  
  18. const int N = 1e5 + 10;
  19. const int M = 1e6 + 5;
  20. const int oo = 1e18;
  21. const int mod = 1e9 + 7;
  22.  
  23. int n, m, sq;
  24. int a[N], dp[N], nxt[N];
  25. int l[N], r[N], st[N];
  26.  
  27. void add(int id, int vl){
  28.      a[id] = vl;
  29.  
  30.      FOD(i, r[id], l[id]){
  31.           if((i + a[i]) / sq != i / sq){
  32.                dp[i] = 1;
  33.                nxt[i] = i + a[i];
  34.                st[i] = i;
  35.           }else{
  36.                dp[i] = dp[i + a[i]] + 1;
  37.                nxt[i] = nxt[i + a[i]];
  38.                st[i] = st[i + a[i]];
  39.           }
  40.      }
  41. }
  42.  
  43. void calc(int id){
  44.      int sl = 0, en = id;
  45.      while(id <= n){
  46.           sl += dp[id];
  47.           en = st[id];
  48.           id = nxt[id];
  49.      }
  50.  
  51.      cout << en << ' ' << sl << '\n';
  52. }
  53.  
  54. void prework(){
  55.      sq = sqrt(n);
  56.  
  57.      l[0] = 1;
  58.      FOR(i, 1, n){
  59.           if(i / sq == (i - 1) / sq){
  60.                l[i] = l[i - 1];
  61.           }else{
  62.                l[i] = i;
  63.           }
  64.      }
  65.      r[n + 1] = n;
  66.      FOD(i, n, 1){
  67.           if(i / sq == (i + 1) / sq){
  68.                r[i] = r[i + 1];
  69.           }else{
  70.                r[i] = i;
  71.           }
  72.      }
  73.  
  74.      FOD(i, n, 1){
  75.           if((i + a[i]) / sq != i / sq){
  76.                dp[i] = 1;
  77.                nxt[i] = i + a[i];
  78.                st[i] = i;
  79.           }else{
  80.                dp[i] = dp[i + a[i]] + 1;
  81.                nxt[i] = nxt[i + a[i]];
  82.                st[i] = st[i + a[i]];
  83.           }
  84.      }
  85. }
  86.  
  87. signed main(){ fast
  88.      if(fopen(FILE ".INP", "r")){
  89.           freopen(FILE".INP", "r", stdin);
  90.           freopen(FILE".OUT", "w", stdout);
  91.      }
  92.  
  93.      cin >> n >> m;
  94.      FOR(i, 1, n) cin >> a[i];
  95.  
  96.      prework();
  97.      FOR(i, 1, m){
  98.           int type; cin >> type;
  99.  
  100.           if(type){
  101.                int id; cin >> id;
  102.                calc(id);
  103.           }else{
  104.                int id, vl;
  105.                cin >> id >> vl;
  106.  
  107.                add(id, vl);
  108.           }
  109.      }
  110. }
  111.  
Success #stdin #stdout 0.01s 5668KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Fm9vSM
language:
C++ (gcc 8.3)
created:
16 hours 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!