Guest User

Untitled

a guest
Jun 12th, 2022
219
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <tuple>
  3. using namespace std;
  4.  
  5. const int N=4;
  6.  
  7. pair<int, int> mx[N*4];
  8.  
  9. void build(int x, int l, int r){
  10.     if (l == r){
  11.         cin >> mx[x].first;
  12.         mx[x].second=l;
  13.         return;
  14.     }
  15.     int mid= (l+r)/2;
  16.     build(x<<1, l, mid);
  17.     build (x<<1|1, mid+1, r);
  18.     mx[x]=max(mx[x<<1], mx[x<<1|1]);
  19. }
  20.  
  21. void update(int x,int l, int r,int p) {
  22.     if(l==r){
  23.         mx[x]={0, 0};
  24.         return;
  25.     }
  26.     int mid=(l+r)/2;
  27.     if(p<=mid)update(x<<1, l, mid, p);
  28.     else update(x<<1|1, mid+1,r, p);
  29.     mx[x]=max(mx[x<<1],mx[x<<1|1]);
  30. }
  31.  
  32. pair<int, int> query (int x, int ql, int qr, int l, int r){
  33.     if(ql==l&&qr==r) return mx[x];
  34.     int mid=(l+r)/2;
  35.     if(qr<=mid)return query(x<<1,ql,qr,l,mid);
  36.     if(ql>mid)return query(x<<1|1, ql,qr,mid+1,r);
  37.     return max(query(x<<1,ql,mid,l,mid),query(x<<1|1,mid+1,qr,mid+1,r));
  38. }
  39.  
  40. int main(){
  41.     build(1, 1, 3);
  42.     int a,b,c,p;
  43.     tie(a, p)=query (1, 1, 3, 1, 3);
  44.     update(1, 1, 3, p);
  45.     tie(b, p)=query (1, 1, 3, 1, 3);
  46.     update(1, 1, 3, p);
  47.     tie(c, p)=query (1, 1, 3, 1, 3);
  48.     update(1, 1, 3, p);
  49.     if(a==b&&b==c) {
  50.         cout<< "3 "<<a<<endl;
  51.     } else if(a==b){
  52.         cout<<"2 "<<a<<" " <<c<<"\n";
  53.     }else if(b-c==0){
  54.         cout<<2<<" "<<a<<" "<<b<<'\n';
  55.     }else {
  56.         cout<<"1 " << a <<' ' <<b<<' '<<c<<endl;
  57.     }
  58. }
  59.  
Advertisement
Add Comment
Please, Sign In to add comment