SHARE
TWEET

Untitled

a guest Jun 14th, 2017 20 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     AUTHOR:hruday pabbisetty
  3.     NIT ROURKElA(My_College_Sucks)
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define opt ios_base::sync_with_stdio(0)
  8. #define lli long long int
  9. #define ulli unsigned long long int
  10. #define I int
  11. #define S string
  12. #define D double
  13. #define rep(i,a,b) for(i=a;i<b;i++)
  14. #define repr(i,a,b) for(i=a;i>b;i--)
  15. #define in(n) scanf("%lld",&n)
  16. #define in2(a,b) scanf("%lld %lld",&a,&b)
  17. #define in3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
  18. #define out(n) printf("%lld",n)
  19. #define inu(a) scanf("%lld",&a)
  20. #define outu(a) printf("%llu",a)
  21. #define ins(s) scanf("%s",&s)
  22. #define outs(s) printf("%s",s)
  23. #define nl printf("\n")
  24. #define mod 1000000007
  25. #define inf 100000000000000
  26. typedef long long       ll;
  27. typedef pair<lli, lli>  plli;
  28. typedef vector<lli>     vlli;
  29. typedef vector<ulli>    vulli;
  30. typedef vector<ll>      vll;
  31. typedef vector<string>  vs;
  32. typedef vector<plli>     vplli;
  33. #define MM(a,x)  memset(a,x,sizeof(a));
  34. #define ALL(x)   (x).begin(), (x).end()
  35. #define P(x)       cerr<<"{"#x<<" = "<<(x)<<"}"<<endl;
  36. #define P2(x,y)       cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<"}"<<endl;
  37. #define P3(x,y,z)  cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<"}"<<endl;
  38. #define P4(x,y,z,w)cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<", "#w" = "<<(w)<<"}"<<endl;
  39. #define PP(x,i)     cerr<<"{"#x"["<<i<<"] = "<<x[i]<<"}"<<endl;
  40. #define TM(a,b)     cerr<<"{"#a" -> "#b": "<<1000*(b-a)/CLOCKS_PER_SEC<<"ms}\n";
  41. #define UN(v)    sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())
  42. #define mp make_pair
  43. #define pb push_back
  44. #define f first
  45. #define s second
  46. #define sz() size()
  47. lli power(lli a,lli b)
  48.     {
  49.     lli value;
  50.     if(b==0)
  51.         {
  52.         return 1;
  53.     }
  54.     else if(b%2==0)
  55.         {
  56.         value=power(a,b/2)%mod;
  57.         return(value*value)%mod;
  58.     }
  59.     else
  60.         {
  61.         value=power(a,b/2)%mod;
  62.         return ((a*value)%mod*(value))%mod;
  63.     }
  64. }
  65. lli a[100005],n,bs=10+sqrt(30000),fre[1000001],cnt=0;
  66. void add(lli idx)
  67. {
  68.     if(fre[a[idx]]==0)
  69.     {
  70.         cnt++;
  71.     //    fre[a[idx]]++;
  72.     }
  73.     fre[a[idx]]++;
  74. }
  75. void rem(lli idx)
  76. {
  77.     fre[a[idx]]--;
  78.     if(fre[a[idx]]==0)
  79.     {
  80.         cnt--;
  81.     }
  82. }
  83. int main()
  84. {
  85.     scanf("%lld",&n);
  86.     lli i;
  87.     rep(i,0,n)
  88.     {
  89.         scanf("%lld",&a[i]);
  90.     }
  91.     vector< pair <plli,lli > >v;
  92.     lli q;
  93.     scanf("%lld",&q);
  94.     lli L[q],R[q];
  95.     rep(i,0,q)
  96.     {
  97.         scanf("%lld %lld",&L[i],&R[i]);
  98.         if(L[i]>R[i])
  99.         {
  100.             swap(L[i],R[i]);
  101.         }
  102.         L[i]--;
  103.         R[i]--;
  104.         v.pb(mp(mp(L[i]/bs,R[i]),i));
  105.     }
  106.     sort(ALL(v));
  107.     lli qr=-1,ql=0,j;
  108.     lli ans[q];
  109.     rep(i,0,q)
  110.     {
  111.         lli l=L[v[i].s];
  112.         lli r=R[v[i].s];
  113.         //cout<<l<<" "<<r<<endl;
  114.         while(qr<r)
  115.         {
  116.             qr++;
  117.             add(qr);
  118.          //   cout<<a[qr]<<" ";
  119.         }
  120.         while(ql>l)
  121.         {
  122.             ql--;
  123.             add(ql);
  124.             //cout<<a[ql]<<" ";
  125.         }
  126.         //cout<<endl;
  127.         while(ql<l)
  128.         {
  129.             rem(ql);
  130.             ql++;
  131.     //        cout<<a[ql]<<" ";
  132.         }
  133.         while(qr>r)
  134.         {
  135.             rem(qr);
  136.             qr--;
  137.   //          cout<<a[qr]<<" ";
  138.         }
  139. //        cout<<endl;
  140.         ans[v[i].s]=cnt;
  141.  
  142.     }
  143.     rep(i,0,q)
  144.     {
  145.         printf("%lld\n",ans[i]);
  146. //        cout<<ans[i]<<endl;
  147.     }
  148. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top