fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. #define ll long long int
  4. #define ull unsigned long long int
  5. #define ld long double
  6. #define cout(var) cout<<var<<endl
  7. #define endl '\n'
  8. #define loop(a,b,c) for(ll i=a;i<=b;i+=c)
  9. #define intarr(arr,n) ll arr[n];for(ll i=0;i<n;i++)cin>>arr[i]
  10. #define inparr(arr,n) for(ll i=0;i<n;i++)cin>>arr[i]
  11. #define inpvec(vec,n) for(ll i=0;i<n;i++){ll var;cin>>var;vec.push_back(var);}
  12. #define pb push_back
  13. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
  14. #define mod 1000000007
  15. #define newline cout<<endl
  16. #define ump unordered_map<ll,ll>
  17. #define vec vector<ll>
  18. #define mkp make_pair
  19. #define disp(var) cout<<var<<" "
  20. bool prime(ll n) 
  21. { 
  22.     if (n <= 1)  return false; 
  23.     if (n <= 3)  return true; 
  24.     if (n%2 == 0 || n%3 == 0) return false; 
  25.  
  26.     for (ll i=5; i*i<=n; i=i+6) 
  27.         if (n%i == 0 || n%(i+2) == 0) 
  28.            return false; 
  29.  
  30.     return true; 
  31. }
  32. ll power(ll x,ll y) 
  33. { 
  34.     ll temp; 
  35.     if(y==0) 
  36.         return 1; 
  37.     temp=power(x,y/2); 
  38.     if (y%2==0) 
  39.         return temp*temp; 
  40.     else
  41.         return x*temp*temp; 
  42. } 
  43. ll no_of_factors(ll n) 
  44. { 
  45.     ll cnt = 0; 
  46.     for (ll i = 1; i <= sqrt(n); i++) 
  47.     { 
  48.         if (n % i == 0) 
  49.         { 
  50.             if (n / i == i) 
  51.                 cnt++; 
  52.  
  53.             else 
  54.                 cnt = cnt + 2; 
  55.         } 
  56.     } 
  57.     return cnt; 
  58. } 
  59. ll gcd(ll a,ll b) 
  60. { 
  61.     if (b==0) 
  62.         return a; 
  63.     return gcd(b,a%b);      
  64. } 
  65. bool subsequence_checker(string str1, string str2, ll m, ll n) 
  66. { 
  67.     if (m == 0) return true; 
  68.     if (n == 0) return false; 
  69.     if (str1[m-1] == str2[n-1]) 
  70.         return subsequence_checker(str1, str2, m-1, n-1); 
  71.     return subsequence_checker(str1, str2, m, n-1); 
  72. }
  73. bool isPowerOfTwo (ll x)  
  74. {  
  75.     return x && (!(x&(x-1)));  
  76. }  
  77. bool incs(ll *a,ll n)
  78. {
  79.     if(n==1)
  80.         return true;
  81.     for(ll i=0;i<n-1;i++)
  82.     {
  83.         if(a[i+1]<=a[i])
  84.             return false;
  85.     }
  86.     return true;
  87. }
  88. bool decs(ll *a,ll n)
  89. {
  90.     if(n==1)
  91.         return true;
  92.     for(ll i=0;i<n-1;i++)
  93.     {
  94.         if(a[i+1]>=a[i])
  95.             return false;
  96.     }
  97.     return true;
  98. }
  99. struct test
  100. {
  101. public:
  102.     ll x,y,z;
  103. };
  104. bool compare(const test &aa,const test &bb)
  105. {
  106.     if(aa.x==bb.x)
  107.     {
  108.         if(aa.y==bb.y)
  109.         {
  110.             return aa.z<bb.z;
  111.         }
  112.         return aa.y<bb.y;
  113.     }
  114.     return aa.x<bb.x;
  115. }
  116.  
  117. ll mm(ll a, ll m=mod) 
  118. { 
  119.     ll m0 = m; 
  120.     ll y = 0, x = 1; 
  121.  
  122.     if (m == 1) 
  123.       return 0; 
  124.  
  125.     while (a > 1) 
  126.     { 
  127.         // q is quotient 
  128.         ll q = a / m; 
  129.         ll t = m; 
  130.  
  131.         // m is remainder now, process same as 
  132.         // Euclid's algo 
  133.         m = a % m, a = t; 
  134.         t = y; 
  135.  
  136.         // Update y and x 
  137.         y = x - q * y; 
  138.         x = t; 
  139.     } 
  140.  
  141.     // Make x positive 
  142.     if (x < 0) 
  143.        x += m0; 
  144.  
  145.     return x; 
  146. } 
  147. ll bs=224;
  148. ll cntt=0;
  149. ll f[1000001]={0};
  150. ll a[200001];
  151. struct query
  152. {
  153.     ll l,r,i;
  154. };
  155. query qu[200001];
  156. ll ans[200001];
  157. ll cnt[2]={0};
  158. bool comp(query a,query b)
  159. {
  160.     if(a.l/bs!=b.l/bs)
  161.     {
  162.         return a.l/bs<b.l/bs;
  163.     }
  164.     return a.r<b.r;
  165. }
  166. void add(ll pos)
  167. {
  168.     if(a[pos]==1)
  169.         cnt[0]++;
  170.     if(a[pos]==-1)
  171.         cnt[1]++;
  172. }
  173. void remove(ll pos)
  174. {
  175.     if(a[pos]==1 && cnt[0]!=0)
  176.         cnt[0]--;
  177.     if(a[pos]==-1 && cnt[1]!=0)
  178.         cnt[1]--;
  179. }
  180. void AcDegaYe()
  181. {
  182.     ll n,q;
  183.     cin>>n>>q;
  184.     for(ll i=0;i<n;i++)
  185.         cin>>a[i];
  186.     //ll q;
  187.     //cin>>q;
  188.     for(ll i=0;i<q;i++)
  189.     {
  190.         cin>>qu[i].l>>qu[i].r;
  191.         qu[i].l--;
  192.         qu[i].r--;
  193.         qu[i].i=i;
  194.     }
  195.     sort(qu,qu+q,comp);
  196.     //ll ans[q];
  197.     ll ml=0,mr=-1;
  198.     //cnt=cnt+f[a[ml]]*f[a[ml]]*a[ml];
  199.     for(ll i=0;i<q;i++)
  200.     {
  201.         ll left=qu[i].l;
  202.         ll right=qu[i].r;
  203.         while(ml>left)
  204.         {
  205.             ml--;
  206.             add(ml);
  207.         }
  208.         while(mr<right)
  209.         {
  210.             mr++;
  211.             add(mr);
  212.         }
  213.         while(ml<left)
  214.         {
  215.             remove(ml);
  216.             ml++;
  217.         }
  218.         while(mr>right)
  219.         {
  220.             remove(mr);
  221.             mr--;
  222.         }
  223.         ans[qu[i].i]=min(cnt[0],cnt[1])*2;
  224.     }
  225.     for(ll i=0;i<q;i++)
  226.     {
  227.         cout(ans[i]);
  228.     }
  229. }
  230.  
  231. int main()
  232. {   
  233.     fastio;
  234.     //ll t;
  235.     //cin>>t;
  236.     ll t=1;
  237.     while(t--)
  238.     {
  239.         AcDegaYe();
  240.     }
  241.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  242.     return 0;
  243. }
Time limit exceeded #stdin #stdout 5s 4516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/33kvC5
problem ZQUERY, based on SPOJ submission 25426446 (CPP14), 2020-02-20 09:13:43
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!