Advertisement
madhukeshk3

Mancunian And Multiplicative Queries-Hackerearth

Aug 31st, 2020
61
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pfi(a) printf("%d",a);
  5. #define pfl(a) printf("%lld",a);
  6. #define pfin(a) printf("%d\n",a);
  7. #define pfln(a) printf("%lld\n",a);
  8. #define pfis(a) printf("%d ",a);
  9. #define pfls(a) printf("%lld ",a);
  10. #define sfi(a) scanf("%d",&a);
  11. #define sfl(a) scanf("%lld",&a);
  12. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  13. #define f(i,a,b) for(int i=a;i<b;i++)
  14. #define pb(a) push_back(a);
  15. #define mp(a,b) make_pair(a,b)
  16. #define ll long long
  17.  
  18. const ll mod=1e9+7;
  19. const int N=50004;
  20.  
  21. int BLOCK;
  22. ll arr[N],func[N];
  23. int freq[1000006]={0};
  24.  
  25. ll prod,ans;
  26.  
  27. struct util
  28. {
  29.     int l,r;
  30. };
  31.  
  32. ll me(ll a, ll n)
  33. {
  34.     ll res=1;
  35.     while(n>0)
  36.     {
  37.         if(n&1) res=(res*a)%mod;
  38.         a=(a*a)%mod;
  39.         n/=2;
  40.     }
  41.     return res;
  42. }
  43.  
  44. ll mi(ll a){
  45.     return me(a, mod-2);
  46. }
  47.  
  48. bool cmp(util a,util b)
  49. {
  50.     int val1=a.l/BLOCK;
  51.     int val2=b.l/BLOCK;
  52.  
  53.     if(val1!=val2)
  54.         return val1<val2;
  55.  
  56.     if(val1%2==1)
  57.         return a.r<b.r;
  58.  
  59.     return b.r>a.r;
  60. }
  61.  
  62. void add(int idx)
  63. {
  64.     prod=(prod*mi(func[freq[arr[idx]]]))%mod;
  65.     freq[arr[idx]]++;
  66.     prod=(prod*func[freq[arr[idx]]])%mod;
  67. }
  68.  
  69. void remove(int idx)
  70. {
  71.     prod=(prod*mi(func[freq[arr[idx]]]))%mod;
  72.     freq[arr[idx]]--;
  73.     prod=(prod*func[freq[arr[idx]]])%mod;
  74. }
  75.  
  76. int main()
  77. {
  78.     int n,c,q;
  79.     sfi(n)
  80.     sfi(c)
  81.     sfi(q)
  82.    
  83.     BLOCK=sqrt(n);
  84.    
  85.     f(i,1,n+1)
  86.         sfl(arr[i])
  87.    
  88.     f(i,0,n+1)
  89.         sfl(func[i])
  90.    
  91.     util queries[q];
  92.    
  93.     f(i,0,q)
  94.     {
  95.         sfi(queries[i].l)
  96.         sfi(queries[i].r)
  97.     }
  98.    
  99.     sort(queries,queries+q,cmp);
  100.    
  101.     int mleft=1,mright=0;
  102.    
  103.     prod=me(func[0],c);
  104.    
  105.     ans=1;
  106.    
  107.     f(i,0,q)
  108.     {
  109.         int left=queries[i].l;
  110.         int right=queries[i].r;
  111.        
  112.         while(mright<right)
  113.         {
  114.             mright++;
  115.             add(mright);
  116.  
  117.         }
  118.         while(mright>right)
  119.         {
  120.             remove(mright);
  121.             mright--;
  122.         }
  123.         while(mleft<left)
  124.         {
  125.             remove(mleft);
  126.             mleft++;
  127.         }
  128.         while(mleft>left)
  129.         {
  130.             mleft--;
  131.             add(mleft);
  132.         }
  133.         ans=(ans*prod)%mod;
  134.     }
  135.    
  136.     pfl(ans)
  137. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement