fork download
copy 
  1. /////////////////////// All Is Well /////////////////////////
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define FOR(i, s, e) for(int i=s; i<e; i++)
  6. #define loop(i, n) for(int i=0; i<n; i++)
  7. #define CIN   ios_base::sync_with_stdio(0); cin.tie(0)
  8. #define getint(n) scanf("%d", &n)
  9. #define pb(a) push_back(a)
  10. #define ll long long int
  11. #define ull unsigned long long int
  12. #define dd double
  13. #define SZ(a) int(a.size())
  14. #define read() freopen("input.txt", "r", stdin)
  15. #define write() freopen("output.txt", "w", stdout)
  16. #define mem(a, v) memset(a, v, sizeof(a))
  17. #define all(v) v.begin(), v.end()
  18. #define pi acos(-1.0)
  19. #define pf printf
  20. #define sf scanf
  21. #define mp make_pair
  22. #define paii pair<int, int>
  23. #define padd pair<dd, dd>
  24. #define pall pair<ll, ll>
  25. #define fr first
  26. #define sc second
  27. #define CASE(n) printf("Case %d: ",++n)
  28. #define CASE_COUT cout<<"Case "<<++cas<<": "
  29. #define inf 1000000000
  30. #define EPS 1e-9
  31.  
  32. using namespace std;
  33.  
  34. //8 way moves
  35. //int fx[]={0,0,1,-1,1,1,-1,-1};
  36. //int fy[]={1,-1,0,0,1,-1,1,-1};
  37.  
  38. //knight moves
  39. //int fx[]={-2,-2,-1,-1,1,1,2,2};
  40. //int fy[]={-1,1,-2,2,-2,2,-1,1};
  41.  
  42. //Bit operation
  43. int SET(int n,int pos)
  44. {
  45.     return n=n | (1<<pos);
  46. }
  47. int RESET(int n,int pos)
  48. {
  49.     return n=n & ~(1<<pos);
  50. }
  51. int CHECK(int n,int pos)
  52. {
  53.     return (bool) (n & (1<<pos));
  54. }
  55.  
  56.  
  57. int bigMod(int n,int power,int MOD)
  58. {
  59.     if(power==0)
  60.         return 1;
  61.     if(power%2==0)
  62.     {
  63.         int ret=bigMod(n,power/2,MOD);
  64.         return ((ret%MOD)*(ret%MOD))%MOD;
  65.     }
  66.     else return ((n%MOD)*(bigMod(n,power-1,MOD)%MOD))%MOD;
  67. }
  68.  
  69. int modInverse(int n,int MOD)
  70. {
  71.     return bigMod(n,MOD-2,MOD);
  72. }
  73.  
  74. int POW(int x, int y)
  75. {
  76.     int res= 1;
  77.     for ( ; y ; )
  78.     {
  79.         if ( (y&1) )
  80.         {
  81.             res*= x;
  82.         }
  83.         x*=x;
  84.         y>>=1;
  85.     }
  86.     return res;
  87. }
  88.  
  89. int inverse(int x)
  90. {
  91.     dd p=((dd)1.0)/x;
  92.     return (p)+EPS;
  93. }
  94.  
  95. int gcd(int a, int b)
  96. {
  97.     while(b) b^=a^=b^=a%=b;
  98.     return a;
  99. }
  100.  
  101. int nC2(int n)
  102. {
  103.     return n*(n-1)/2;
  104. }
  105.  
  106. int MOD(int n,int mod)
  107. {
  108.     if(n>=0)
  109.         return n%mod;
  110.     else if(-n==mod)
  111.         return 0;
  112.     else
  113.         return mod+(n%mod);
  114. }
  115.  
  116. const int mx=100005;
  117.  
  118. int data[mx];
  119.  
  120. vector< paii >tree[350];
  121.  
  122.  
  123. int getid(int i,int blck)
  124. {
  125.     return i/blck;
  126. }
  127.  
  128. void init(int blck,int n)
  129. {
  130.     int cnt=0;
  131.     for(int i=0; i<=blck; i++)
  132.     {
  133.         int p=0;
  134.         for(int j=0; j<blck; j++)
  135.         {
  136.             if(cnt>=n)
  137.                 break;
  138.             tree[i].pb(mp(data[cnt],cnt));
  139.             cnt++;
  140.             p++;
  141.         }
  142.         if(p)
  143.             sort(all(tree[i]));
  144.     }
  145. }
  146.  
  147. void update(int ind,int x,int blck)
  148. {
  149.     int blckid=getid(ind,blck);
  150.     for(int i=0; i<tree[blckid].size(); i++)
  151.     {
  152.         if(tree[blckid][i].sc==ind)
  153.         {
  154.             tree[blckid][i].fr=x;
  155.             break;
  156.         }
  157.     }
  158.     sort(all(tree[blckid]));
  159. }
  160.  
  161. int BS(int left,int right,int x,int blckid)
  162. {
  163.     int mid=(left+right)/2;
  164.     int ans=right;
  165.     while(left<=right)
  166.     {
  167.         if(tree[blckid][mid].fr<x)
  168.         {
  169.             left=mid+1;
  170.         }
  171.         else
  172.         {
  173.             right=mid-1;
  174.             ans=mid;
  175.         }
  176.     }
  177.     return ans;
  178. }
  179.  
  180. int query(int left,int right,int x,int blck)
  181. {
  182.     int leftid=getid(left,blck);
  183.     int rightid=getid(right,blck);
  184.     if(leftid==rightid)
  185.     {
  186.         int cnt=0;
  187.         for(int i=0; i<tree[leftid].size(); i++)
  188.         {
  189.             if(tree[leftid][i].sc>=left && tree[rightid][i].sc<=right && tree[leftid][i].fr<=x)
  190.                 cnt++;
  191.         }
  192.         return cnt;
  193.     }
  194.     if(leftid+1==rightid)
  195.     {
  196.         int cnt=0;
  197.         for(int i=0; i<tree[leftid].size(); i++)
  198.         {
  199.             if(tree[leftid][i].sc>=left &&  tree[leftid][i].fr<=x)
  200.                 cnt++;
  201.         }
  202.         for(int i=0; i<tree[rightid].size(); i++)
  203.         {
  204.             if(tree[rightid][i].sc<=right && tree[rightid][i].fr<=x)
  205.                 cnt++;
  206.         }
  207.         return cnt;
  208.     }
  209.     int cnt=0;
  210.     for(int i=0; i<tree[leftid].size(); i++)
  211.     {
  212.         if(tree[leftid][i].sc>=left && tree[leftid][i].fr<=x)
  213.             cnt++;
  214.     }
  215.  
  216.     for(int i=leftid+1;i<rightid;i++)
  217.     {
  218.         int pp=BS(0,blck-1,x,i);
  219.         if(tree[i][pp].fr==x || pp==blck-1)
  220.             pp++;
  221.         cnt+=pp;
  222.     }
  223.  
  224.     for(int i=0; i<tree[rightid].size(); i++)
  225.     {
  226.         if( tree[rightid][i].sc<=right && tree[rightid][i].fr<=x)
  227.             cnt++;
  228.     }
  229.     return cnt;
  230. }
  231.  
  232. int main()
  233. {
  234.     int t,cas=0;
  235.     int n,q;
  236.     sf("%d %d",&n,&q);
  237.     int blck=sqrt(n);
  238.     loop(i,n)
  239.     {
  240.         getint(data[i]);
  241.     }
  242.  
  243.     init(blck,n);
  244. //    for(int i=0;i<blck;i++)
  245. //    {
  246. //        for(int j=0;j<tree[i].size();j++)
  247. //            cout<<tree[i][j].fr<<" ";
  248. //        cout<<endl;
  249. //    }
  250.     while(q--)
  251.     {
  252.         getchar();
  253.         char cc;
  254.         int p,qq,x;
  255.         sf("%c",&cc);
  256.         if(cc=='M')
  257.         {
  258.             sf("%d %d",&p,&x);
  259.             update(p-1,x,blck);
  260.         }
  261.         else
  262.         {
  263.             sf("%d %d %d",&p,&qq,&x);
  264.             pf("%d\n",query(p-1,qq-1,x,blck));
  265.         }
  266.     }
  267.  
  268.     return  0;
  269.  
  270. }
  271.  
Time limit exceeded #stdin #stdout 5s 3808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LauRKN
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!