Advertisement
Saleh127

sparse table template AK

Aug 7th, 2022
785
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.02 KB | None | 0 0
  1. /***
  2.  created: 2022-08-07-23.28.09
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10. template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
  11. #define ll long long
  12. #define int ll
  13. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  14. #define get_lost_idiot return 0
  15. #define nl '\n'
  16.  
  17. const ll lim=200005;
  18. const ll inf=-2e18;
  19.  
  20. int a[lim],psum[lim],ssum[lim];
  21.  
  22. struct Sparse
  23. {
  24.     int n,lg;
  25.     vector<vector<int> >sparse_mx,sparse_mn;
  26.     vector<int>A;
  27.     void init(int tmp)
  28.     {
  29.         n=tmp;
  30.         A.resize(n+3);
  31.         lg=32-__builtin_clz(n+2);// 64 if nmx > 10^9
  32.         sparse_mx=vector< vector<int> >(n+2,vector<int>(lg));
  33.  
  34.     }
  35.     void abr_init(int aa[])
  36.     {
  37.         for(int i=1; i<=n; i++)A[i]=aa[i];
  38.         build_table();
  39.     }
  40.     void build_table()
  41.     {
  42.         for(int i=1; i<=n; i++)sparse_mx[i][0]=A[i];
  43.         for(int k=1,p=1; k<lg; k++,p<<=1)
  44.         {
  45.             for(int i=1; i+p+p<=n+1; i++)
  46.             {
  47.                 sparse_mx[i][k]=max(sparse_mx[i][k-1],sparse_mx[i+p][k-1]);
  48.  
  49.             }
  50.         }
  51.     }
  52.     int qmx(int l,int r)
  53.     {
  54.         int len=r-l+1;
  55.         int k=32-__builtin_clz(len)-1;
  56.         return max(sparse_mx[l][k],sparse_mx[r-(1<<k)+1][k]);
  57.     }
  58.  
  59.  
  60.  
  61. };
  62.  
  63.  
  64. main()
  65. {
  66.     ios_base::sync_with_stdio(0);
  67.     cin.tie(0);
  68.     cout.tie(0);
  69.  
  70.     test
  71.     {
  72.         ll n,m,i,j,k,l,ans=0;
  73.  
  74.         Sparse sa,sp,ss;
  75.  
  76.         cin>>n;
  77.  
  78.         for(i=1; i<=n; i++) cin>>a[i];
  79.  
  80.         k=0;
  81.  
  82.         for(i=1;i<=n;i++)
  83.         {
  84.             k+=a[i];
  85.             psum[i]=k;
  86.         }
  87.  
  88.         k=0;
  89.  
  90.         for(i=n;i>=1;i--)
  91.         {
  92.             k+=a[i];
  93.             ssum[i]=k;
  94.         }
  95.  
  96.         ssum[n+1]=0;
  97.  
  98.         sa.init(n);
  99.         sa.abr_init(a);
  100.         sp.init(n);
  101.         sp.abr_init(psum);
  102.         ss.init(n);
  103.         ss.abr_init(ssum);
  104.  
  105.  
  106.         for(i=1; i<=n; i++)
  107.         {
  108.             ll lo=1,hi=i;
  109.  
  110.             while(lo<hi)
  111.             {
  112.                 ll mid=(lo+hi)/2;
  113.  
  114.                 ll mx=sa.qmx(mid,i);
  115.  
  116.                 if(mx<=a[i])
  117.                 {
  118.                     hi=mid;
  119.                 }
  120.                 else lo=mid+1;
  121.             }
  122.  
  123.             ll lft=hi;
  124.  
  125.             lo=i,hi=n;
  126.  
  127.             while(lo<hi)
  128.             {
  129.                 ll mid=(lo+hi+1)/2;
  130.  
  131.                 ll mx=sa.qmx(i,mid);
  132.  
  133.                 if(mx<=a[i])
  134.                 {
  135.                     lo=mid;
  136.                 }
  137.                 else hi=mid-1;
  138.             }
  139.  
  140.             ll rgt=lo;
  141.  
  142.             ll rtmx = sp.qmx(i,rgt)-psum[i-1];
  143.             ll lfmx = ss.qmx(lft,i)-ssum[i+1];
  144.  
  145.             ll z=rtmx+lfmx-a[i];
  146.  
  147.             if(z>a[i])
  148.             {
  149.                 ans=1;
  150.                 break;
  151.             }
  152.  
  153.         }
  154.  
  155.         if(ans==0) cout<<"YES"<<nl;
  156.         else cout<<"NO"<<nl;
  157.  
  158.     }
  159.  
  160.     get_lost_idiot;
  161. }
  162.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement