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.  
  9. ll getmax(ll a,ll b){
  10.     return a>b?a:b;
  11. }
  12.  
  13. ll getmin(ll a,ll b){
  14.     return a<b?a:b;
  15. }
  16.  
  17. void implement(int l,int r,int i){
  18.     if(l==r){
  19.         tree[i].insert(arr[l]);
  20.         return;
  21.     }
  22.     int m=(l+r)/2;
  23.     implement(l,m,i*2+1);
  24.     implement(m+1,r,i*2+2);
  25.     tree[i]=tree[i*2+1];
  26.     for(int f=m+1;f<=r;f++)tree[i].insert(arr[f]);
  27. }
  28.  
  29. void update(int l,int r,int i){
  30.     if(l>pos||r<pos)return;
  31.     tree[i].insert(val);
  32.     tree[i].erase(del);
  33.     if(l==r){
  34.         return;
  35.     }
  36.     int m=(l+r)/2;
  37.     update(l,m,i*2+1);
  38.     update(m+1,r,i*2+2);
  39. }
  40.  
  41. ll solve(int l,int r,int i){
  42.     if(l>r1||r<l1||(k>*(--tree[i].end())))return LLONG_MAX;
  43.     if(l>=l1&&r<=r1){
  44.         return *tree[i].lower_bound(k);
  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 brute_force()
  51. {
  52.     ll answer = LLONG_MAX;
  53.  
  54.     for (int i = l1; i <= r1; i++)
  55.         if (arr[i] >= k && answer > arr[i])
  56.             answer = arr[i];
  57.     return answer;
  58. }
  59.  
  60. int main(){
  61.     FAST_IO;
  62.     ll s;
  63.     int n,m,t;
  64.     //cin>>n>>m;
  65.     n = 10;
  66.     m = 100;
  67.     arr.resize(n);
  68.     //for(auto &x:arr)cin>>x;
  69.     for(auto &x:arr) x = rand() % 20;
  70.     tree.resize(4*n+1);
  71.     implement(0,n-1,0);
  72.     while(m--){
  73.         //cin>>t;
  74.         t = rand() % 2;
  75.         if(t==1){
  76.             //cin>>pos>>val;
  77.             pos = rand() % n + 1;
  78.             val = rand() % 20;
  79.             pos--;
  80.             del=arr[pos];
  81.             update(0,n-1,0);
  82.             arr[pos]=val;
  83.         } else {
  84.             //cin>>l1>>r1>>k;
  85.             l1 = rand()%n + 1;
  86.             r1 = rand()%n + 1;
  87.             k = rand()%20;
  88.             l1--;
  89.             r1--;
  90.             s=solve(0,n-1,0);
  91.             if(s==LLONG_MAX)cout<<-1<<endl;
  92.             else cout<<s<<endl;
  93.  
  94.             ll s2 = brute_force();
  95.             if(s2==LLONG_MAX)cout<<"Correct: " << -1<<endl<<endl;
  96.             else cout<<"Correct: " <<s2<<endl<<endl;
  97.         }
  98.     }
  99. }
Runtime error #stdin #stdout 0.01s 5540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
Correct: -1

13
Correct: 13

9
Correct: 9

15
Correct: 15

9
Correct: 9

-1
Correct: -1

15
Correct: 15

-1
Correct: -1

-1
Correct: -1

15
Correct: 11

-1
Correct: -1
https://ideone.com/Gud18G
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!