fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,q,p[500005],st[2][2000006];
  5. void UPDATE1(int id, int l, int r, int i, int v)
  6. {
  7.     if (l>i || r<i) return;
  8.     else if (l==r)
  9.     {
  10.         st[0][id]=v;
  11.         return;
  12.     }
  13.     int mid=(l+r)/2;
  14.     if (i<=mid) UPDATE1(id*2,l,mid,i,v);
  15.     else UPDATE1(id*2+1,mid+1,r,i,v);
  16.     st[0][id]=min(st[0][id*2],st[0][id*2+1]);
  17. }
  18. void UPDATE2(int id, int l, int r, int i, int v)
  19. {
  20.     if (l>i || r<i) return;
  21.     else if (l==r)
  22.     {
  23.         st[1][id]=v;
  24.         return;
  25.     }
  26.     int mid=(l+r)/2;
  27.     if (i<=mid) UPDATE2(id*2,l,mid,i,v);
  28.     else UPDATE2(id*2+1,mid+1,r,i,v);
  29.     st[1][id]=min(st[1][id*2],st[1][id*2+1]);
  30. }
  31. int GET1(int id, int l, int r, int u, int v)
  32. {
  33.     if (l>v || r<u) return 1e18;
  34.     else if (l>=u && r<=v) return st[0][id];
  35.     int mid=(l+r)/2;
  36.     return min(GET1(id*2,l,mid,u,v),GET1(id*2+1,mid+1,r,u,v));
  37. }
  38. int GET2(int id, int l, int r, int u, int v)
  39. {
  40.     if (l>v || r<u) return 1e18;
  41.     else if (l>=u && r<=v) return st[1][id];
  42.     int mid=(l+r)/2;
  43.     return min(GET2(id*2,l,mid,u,v),GET2(id*2+1,mid+1,r,u,v));
  44. }
  45. void UPDATE1(int i, int v)
  46. {
  47.     UPDATE1(1,1,n,i,v);
  48.     return;
  49. }
  50. void UPDATE2(int i, int v)
  51. {
  52.     UPDATE2(1,1,n,i,v);
  53.     return;
  54. }
  55. int GET1(int l, int r)
  56. {
  57.     return GET1(1,1,n,l,r);
  58. }
  59. int GET2(int l, int r)
  60. {
  61.     return GET2(1,1,n,l,r);
  62. }
  63. signed main()
  64. {
  65.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  66.     cin>>n>>q;
  67.     for (int i=1;i<=n;i++) cin>>p[i],UPDATE1(i,p[i]-i),UPDATE2(i,p[i]+i);
  68.     for (int i=1;i<=q;i++)
  69.     {
  70.         int t,k,x;
  71.         cin>>t;
  72.         if (t==1) 
  73.         {
  74.             cin>>k>>x;
  75.             UPDATE1(k,x-k),UPDATE2(k,x+k);
  76.         }
  77.         else
  78.         {
  79.             cin>>k;
  80.             cout<<min(GET1(1,k)+k,GET2(k+1,n)-k)<<'\n';
  81.         }
  82.     }
  83.     return 0;
  84. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rqxIgi
language:
C++14 (gcc 8.3)
created:
1 day 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!