Rishav_hitk_cse

Power of three

Apr 12th, 2021
530
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3.     const int mod = 3;
  4.     vector<int> tree;
  5.     void build(vector<int> &a,int v,int l,int r){
  6.         if(l==r)
  7.             tree[v] = a[l];
  8.         else{
  9.             int mid = (l+r)/2;
  10.             build(a,2*v,l,mid);
  11.             build(a,2*v+1,mid+1,r);
  12.             tree[v] = (tree[2*v]+tree[2*v+1])%3;
  13.         }
  14.     }
  15.     int range_sum(int v,int tl,int tr,int l,int r){
  16.         if(l>r)
  17.             return 0;
  18.         if(l==tl and r==tr)
  19.             return tree[v];
  20.         int tm = (tl+tr)/2;
  21.         return (range_sum(2*v,tl,tm,l,min(tm,r))+range_sum(2*v+1,tm+1,tr,max(l,tm+1),r))%3;
  22.     }
  23.     void update(int v,int tl,int tr,int idx,int val){
  24.         if(tl == tr)
  25.             tree[v] = val;
  26.         else{
  27.             int tm = (tl+tr)/2;
  28.             if(idx<=tm)
  29.                 update(2*v,tl,tm,idx,val);
  30.             else
  31.                 update(2*v+1,tm+1,tr,idx,val);
  32.             tree[v] = (tree[2*v]+tree[2*v+1])%3;
  33.         }
  34.     }
  35.     vector<int> Solution::solve(string s, vector<vector<int> > &queries) {
  36.         const int n = s.size();
  37.         tree.assign(4*n,0);
  38.         vector<int> power(n);
  39.         vector<int> a(n);
  40.         power[0] = 1;
  41.         for(int i=1;i<n;i++){
  42.             power[i] = (power[i-1]*2)%mod;
  43.         }
  44.         reverse(power.begin(),power.end());
  45.         for(int i=0;i<n;i++){
  46.             if(s[i]=='1')
  47.                 a[i] = power[i];
  48.         }
  49.        
  50.         build(a,1,0,n-1);
  51.         vector<int> ans;
  52.         for(auto &q:queries){
  53.             int x = q[0],u = q[1]-1,v = q[2]-1;
  54.             if(x){
  55.                 if(s[u]=='0'){
  56.                     s[u] = '1';
  57.                     a[u] = power[u];
  58.                     update(1,0,n-1,u,power[u]);
  59.                 }
  60.                 ans.push_back(-1);
  61.             }else{
  62.                 int curr = range_sum(1,0,n-1,u,v);
  63.                 ans.push_back((curr*power[v])%3);
  64.             }
  65.         }
  66.         return ans;
  67.     }
  68.  
  69.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×