fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
  5. vector<multiset<ll>>tree;
  6. vector<ll>arr;
  7. ll pos,val,del,k,l1,r1;
  8. ll getmax(ll a,ll b){
  9.     return a>b?a:b;
  10. }
  11.  
  12. ll getmin(ll a,ll b){
  13.     return a<b?a:b;
  14. }
  15.  
  16. void implement(int l,int r,int i){
  17.     if(l==r){
  18.         tree[i].insert(arr[l]);
  19.         return;
  20.     }
  21.     int m=(l+r)/2;
  22.     implement(l,m,i*2+1);
  23.     implement(m+1,r,i*2+2);
  24.     tree[i]=tree[i*2+1];
  25.     for(int f=m+1;f<=r;f++)tree[i].insert(arr[f]);
  26. }
  27.  
  28. void update(int l,int r,int i){
  29.     if(l>pos||r<pos)return;
  30.     tree[i].erase(arr[pos]);
  31.     tree[i].insert(val);
  32.     if(l==r){
  33.         return;
  34.     }
  35.     int m=(l+r)/2;
  36.     update(l,m,i*2+1);
  37.     update(m+1,r,i*2+2);
  38. }
  39.  
  40. ll solve(int l,int r,int i){
  41.     if(l>r1||r<l1)return LLONG_MAX;
  42.     if(l>=l1&&r<=r1){
  43.         auto it=tree[i].lower_bound(k);
  44.         return it==tree[i].end() ? LLONG_MAX:(*it);
  45.     }
  46.     int m=(l+r)/2;
  47.     return getmin(solve(l,m,i*2+1),solve(m+1,r,i*2+2));
  48. }
  49.  
  50. int main(){
  51.     FAST_IO;
  52.     ll s;
  53.     int n,m,t;
  54.     cin>>n>>m;
  55.     arr.resize(n);
  56.     for(auto &x:arr)cin>>x;
  57.     tree.resize(4*n+1);
  58.     implement(0,n-1,0);
  59.     while(m--){
  60.         cin>>t;
  61.         if(t==1){
  62.             cin>>pos>>val;
  63.             pos--;
  64.             update(0,n-1,0);
  65.             arr[pos]=val;
  66.         } else {
  67.             cin>>l1>>r1>>k;
  68.             l1--;
  69.             r1--;
  70.             s=solve(0,n-1,0);
  71.             if(s==LLONG_MAX)cout<<-1; else 
  72.             cout<<s;
  73.             cout<<endl;
  74.         }
  75.     }
  76. }
Runtime error #stdin #stdout 0.01s 5380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6DtYsJ
language:
C++ (gcc 8.3)
created:
2 years 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!