Guest User

Untitled

a guest
Feb 23rd, 2018
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <iostream>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. #define ll long long
  7. #define Max(a,b) ((a>=b)? a : b)
  8. #define Min(a,b) ((a<=b)? a : b)
  9. #define pb push_back
  10. #define MOD 1000000007
  11. #define MP make_pair
  12. #define vi vector<int>
  13. #define vll vector<ll>
  14. #define MAX 1123456
  15. //typedef __int128 bigll;
  16. int a[1002][1002];
  17. int bit[1002][1002];
  18.  
  19. int query_sum(int x,int y)
  20. {
  21. int ret=0;
  22. if(x<0 || y<0)return 0;
  23. for(int i=x; i>=0; i=(i&(i+1))-1)
  24. for(int j=y; j>=0; j=(j&(j+1))-1)
  25. ret+=bit[i][j];
  26. return ret;
  27. }
  28.  
  29. void update(int x,int y,int val)
  30. {
  31. for (int i = x; i <=1000; i = i | (i+1))
  32. for (int j = y; j <=1000 ; j = j | (j+1))
  33. bit[i][j] += val;
  34. }
  35.  
  36. int get_sum(int x,int y,int l,int r)
  37. {
  38. return query_sum(l,r) - query_sum(x-1,r) - query_sum(l,y-1) + query_sum(x-1,y-1);
  39. }
  40.  
  41. int main()
  42. {
  43. //ios_base::sync_with_stdio(false);
  44. //cin.tie(NULL);
  45. //FILE*f=freopen("input.txt","r",stdin);
  46. //FILE*o=freopen("output.txt","w",stdout);
  47. int x,y,t,q,l,r,c;
  48. scanf("%d",&t);
  49. for(int tc=1;tc<=t;tc++)
  50. {
  51. memset(bit,0,sizeof(bit));
  52. memset(a,0,sizeof(a));
  53. printf("Case %d:\n",tc);
  54. scanf("%d",&q);
  55. while(q--)
  56. {
  57. scanf("%d",&c);
  58. if(c==0)
  59. {
  60. scanf("%d %d",&x,&y);
  61. if(a[x][y]!=1)
  62. {
  63. a[x][y]=1;
  64. update(x,y,1);
  65. }
  66. }
  67. else
  68. {
  69. scanf("%d %d %d %d",&x,&y,&l,&r);
  70. printf("%d\n",get_sum(x,y,l,r));
  71. }
  72. }
  73. }
  74. //fclose(f);
  75. //fclose(o);
  76.  
  77. return 0;
  78. }
Add Comment
Please, Sign In to add comment