fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;int n;
  3. int tknp(int a[],int k)
  4. {
  5.     int l=1;int r=n;
  6.     while(l<=r) {
  7.         int mid=(l+r)/2;
  8.         if(a[mid]<k) l=mid+1;else
  9.         if(a[mid]>k) r=mid-1;else
  10.         return mid;
  11.     }
  12. }
  13. void insertionSort(int arr[], int n,int mx)
  14. {
  15.     int i=n, key, j;
  16.         key = arr[i];
  17.         j = i - 1 ;
  18.         while (j >= 1 && arr[j] > key)
  19.             arr[j + 1] = arr[j--];
  20.         arr[j+1] = key;
  21.         key = arr[i];
  22.         while (i < mx && arr[i+1] < key)
  23.             arr[i] = arr[++i];
  24.         arr[i]=key;
  25. }
  26. int main()
  27. {
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(0);cout.tie(0);
  30.     int q,a[300001],b[300001];
  31.     cin >> n>> q;
  32.     for(int i=1;i<=n;i++) {cin >> b[i];a[i]=b[i];}
  33.     sort(b+1,b+n+1);
  34.     for(int i=1;i<=q;i++) {
  35.         int id,x;
  36.         cin >> id>>x;                                   
  37.         int y=tknp(b,a[id]);b[y]=x;
  38.         insertionSort(b,y,n);
  39.         cout<<b[(n+1)/2]<<" ";
  40.         a[id]=x;
  41.     }
  42. }
  43.  
Success #stdin #stdout 0.01s 5444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qwSp36
language:
C++ (gcc 8.3)
created:
2 years 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!