fork download
copy 
  1. #include <stdio.h>
  2. #define MAXN 1000010
  3. #define LL long long
  4. LL tree[MAXN];
  5. // THIS SHOULD BE WRONG BUT GIVES ACCEPTED
  6. /*LL read(int idx) {
  7. LL sum = 0;
  8. while (idx > 0) {
  9. sum += tree[idx];
  10. idx -= (idx & -idx);
  11. }
  12. return sum;
  13. }*/
  14. // ACCORDING TO ME THIS IS RIGHT BUT GIVE WRONG ANS
  15. LL read(int idx){
  16. LL sum = tree[idx]; // sum will be decreased
  17. if (idx > 0){ // special case
  18.     int z = idx - (idx & -idx); // make z first
  19. 	idx--; // idx is no important any more, so instead y, you can use idx
  20. 	while (idx != z){ // at some iteration idx (y) will become z
  21. 		sum -= tree[idx]; 
  22. // substruct tree frequency which is between y and "the same path"
  23. 		idx -= (idx & -idx);
  24. 	}
  25. }
  26. return sum;
  27. }
  28. void update(int idx, LL val) {
  29. while (idx <= MAXN) {
  30. tree[idx] += val;
  31. idx += (idx & -idx);
  32. }
  33. }
  34.  
  35. inline void scan(int *a) {
  36. register char c=0;
  37. while (c < 33)
  38. c = getchar_unlocked();
  39. *a = 0;
  40. while (c > 33) {
  41. *a = *a * 10 + c - '0';
  42. c = getchar_unlocked();
  43. }
  44. }
  45.  
  46. LL in(){LL r=0,c;for(c=getchar_unlocked();c<=32;c=getchar_unlocked());if(c=='-') return -in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar_unlocked());return r;}
  47.  
  48. main()
  49. {
  50. int n, m;
  51. LL c;
  52. char ch;
  53. scan(&n);
  54. scan(&m);
  55. c = in();
  56. while (m--)
  57. {
  58.  ch = getchar();
  59.  while (ch != 'Q' && ch != 'S' )
  60.   ch = getchar();
  61.   if (ch == 'Q' )
  62.   {
  63.   int p;
  64.   scan(&p);
  65.   printf("%lld\n", read(p) + c);
  66.   }
  67. else
  68.  {
  69.   int u, v;
  70.   LL k;
  71.   scan(&u);
  72.   scan(&v);
  73.   k = in();
  74.   update(u, k);///update from u to MAXVAL but we want from
  75. /// u till v ...so subtract from v+1 till MAXVAL
  76.   update(v+1, -k);
  77.  }
  78.  
  79. }
  80. return 0;
  81. }
  82.  
Success #stdin #stdout 0s 10672KB
comments (?)
stdin
copy 
7 5 0
Q 7
S 1 7 1
Q 3
S 1 3 1
Q 3
stdout
copy 
0
0
0
https://ideone.com/GQGgTx
language:
C++ (gcc 8.3)
created:
11 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!