fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pii pair<int,int>
  5. #define pll pair<ll,ll>
  6. #define fi first
  7. #define se second
  8. #define FOR(i,k,n) for(int i =(k),_n=(n); i<=_n; i++)
  9. #define FOD(i,k,n) for(int i =(k),_n=(n); i>=_n; i--)
  10. #define pb push_back
  11. const int maxn =1e5+6;
  12. int a[maxn],mx[4*maxn],n,t,lz[4*maxn];
  13. void build(int id, int l,int r){
  14.     if ( l > r) return;
  15.     if ( l== r){
  16.         mx[id]=a[l];
  17.         return;
  18.     }
  19.     int mid =(l+r)/2;
  20.     build(2*id,l,mid);
  21.     build(2*id+1,mid+1,r);
  22.     mx[id]=max(mx[2*id],mx[2*id+1]);
  23. }
  24. void pus(int id, int l ,int r){
  25.     if (lz[id]){
  26.             mx[id]=lz[id];
  27.             if (l == r){
  28.                 lz[2*id]=lz[id];
  29.                 lz[2*id+1]=lz[id];
  30.             }
  31.             lz[id]=0;
  32.                 }
  33. }
  34. void upd(int id, int l, int r, int u, int v, int w){
  35.     if ( l > v || r < u) return;
  36.     if ( l >= u&& r <=v) {
  37.         lz[id]=w;
  38.         pus(id,l,r);
  39.         return;
  40.     }
  41.     int mid =(l+r)/2;
  42.     upd(2*id,l,mid,u,v,w);
  43.     upd(2*id+1,mid+1,r,u,v,w);
  44.     mx[id]=max(mx[2*id],mx[2*id+1]);
  45. }
  46. int query(int id,int l, int r, int u, int v){
  47.     if ( l > v || r < u) return INT_MIN;
  48.     if ( l >= u && r <=v) return mx[id];
  49.     int mid =(l+r)/2;
  50.     int q1=query(2*id,l,mid,u,v);
  51.     int q2=query(2*id+1,mid+1,r,u,v);
  52.     return max(q1,q2);
  53. }
  54. int main(){
  55.     ios_base::sync_with_stdio(false);cin.tie(NULL);
  56.     cin >> n;
  57.     FOR(i,1,n) cin >> a[i];
  58.     build(1,1,n);
  59.     cin >> t;
  60.     build(1,1,n);
  61.     FOR(i,1,t){
  62.         int type;
  63.         cin >> type;
  64.         if (type ==1){
  65.             int u,v,w;
  66.             cin >> u >> v >> w;
  67.             upd(1,1,n,u,v,w);
  68.         }
  69.         else{
  70.             int u,v;
  71.             cin >> u >> v;
  72.             cout << query(1,1,n,u,v) << endl;
  73.         }
  74.     }
  75. }
  76.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/n8RuaT
language:
C++14 (gcc 8.3)
created:
8 days 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!