Guest User

Untitled

a guest
Apr 11th, 2015
207
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.72 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:100000000")
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <memory.h>
  5. #include <cstring>
  6. #include <sstream>
  7. #include <cstdlib>
  8. #include <complex>
  9. #include <string>
  10. #include <bitset>
  11. #include <vector>
  12. #include <cstdio>
  13. #include <ctime>
  14. #include <cmath>
  15. #include <queue>
  16. #include <stack>
  17. #include <set>
  18. #include <map>
  19.  
  20. using namespace std;
  21.  
  22. typedef long long ll;
  23. typedef long double ld;
  24. typedef unsigned long long ull;
  25. typedef complex < double > cd;
  26.  
  27. const bool db = false;
  28.  
  29. #define mp make_pair
  30. #define pb push_back
  31. #define ppb pop_back
  32. #define sd second
  33. #define fs first
  34.  
  35. #define inf 1000000007
  36. #define nmax 100010
  37. #define mmax 100010
  38. #define eps 1e-9
  39.  
  40. const int Magic = 1801, Size = 1010;
  41.  
  42. ll s[Size][Size], inc[Size][Size], ans;
  43. int chlx[Magic], chly[Magic];
  44. int chrx[Magic], chry[Magic], chv[Magic];
  45. int cur, n, m, pt;
  46. int q, lx, ly, rx, ry, f, v;
  47.  
  48. inline ll Get(int Lx, int Ly, int Rx, int Ry) {
  49. return s[Rx][Ry] - s[Lx - 1][Ry] - s[Rx][Ly - 1] + s[Lx - 1][Ly - 1];
  50. }
  51.  
  52. void Rebuild() {
  53. for(int i = 0; i <= n + 1; ++i)
  54. for(int j = 0; j <= m + 1; ++j)
  55. inc[i][j] = 0;
  56. for(int i = n; i >= 1; --i)
  57. for(int j = m; j >= 1; --j)
  58. s[i][j] -= s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
  59. for(int i = 1; i <= pt; ++i) {
  60. lx = chlx[i]; ly = chly[i];
  61. rx = chrx[i]; ry = chry[i];
  62. inc[lx][ly] += chv[i];
  63. inc[rx + 1][ly] -= chv[i];
  64. inc[lx][ry + 1] -= chv[i];
  65. inc[rx + 1][ry + 1] += chv[i];
  66. }
  67. for(int i = 1; i <= n; ++i)
  68. for(int j = 1; j <= m; ++j) {
  69. inc[i][j] += inc[i - 1][j] + inc[i][j - 1] - inc[i - 1][j - 1];
  70. s[i][j] = s[i][j] + inc[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
  71. }
  72. }
  73.  
  74. int main() {
  75. //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  76. //freopen("a.in", "r", stdin); freopen("a.out", "w", stdout);
  77. //ios :: sync_with_stdio(false);
  78. scanf("%d%d%d", &n, &m, &q);
  79. while(q --> 0) {
  80. scanf("%d%d%d%d%d", &f, &lx, &ly, &rx, &ry);
  81. if(f == 1) {
  82. scanf("%d", &v); ++pt;
  83. chlx[pt] = lx; chly[pt] = ly; chrx[pt] = rx; chry[pt] = ry; chv[pt] = v;
  84. if(pt + 1 == Magic) {
  85. Rebuild();
  86. pt = 0;
  87. }
  88. } else {
  89. ans = Get(lx, ly, rx, ry);
  90. for(int i = 1; i <= pt; ++i) {
  91. int X = min(chrx[i], rx) - max(chlx[i], lx) + 1; if(X < 0) X = 0;
  92. int Y = min(chry[i], ry) - max(chly[i], ly) + 1; if(Y < 0) Y = 0;
  93. ans += chv[i] * 1LL * X * 1LL * Y;
  94. }
  95. printf("%lld\n", ans);
  96. }
  97. }
  98. cin.get(); cin.get();
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment