fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define jjs(i, s, x) for (int i = (s); i < (x); i++)
  4. #define jjl(i, x) jjs(i, 0, x)
  5. #define ji(x) jjl(i, x)
  6. #define jj(x) jjl(j, x)
  7. #define jk(x) jjl(k, x)
  8. #define jij(a, b) ji(a) jj(b)
  9. #define ever ;;
  10. #define foreach(x, C) for (auto& x : (C))
  11. #define INF ((int) 1e9+10)
  12. #define LINF ((ll) 1e16)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define rint(x) scanf("%d", &(x))
  16. #define rlong(x) scanf("%lld", &(x))
  17. #define nrint(x) int x; rint(x);
  18. #define nrlong(x) long long x; rlong(x);
  19. #define rfloat(x) scanf("%lf", &(x))
  20.  
  21. const int MOD = 1000000007;
  22. using namespace std;
  23. typedef long long ll;
  24. typedef pair<int, int> pi;
  25.  
  26. const int MX = 2010;
  27. ll answer[MX][MX];
  28. int N;
  29. int arr[MX];
  30. int buf[MX];
  31. map<int, int> idxMap;
  32. ll bit[5][MX];
  33.  
  34. ll read(int b, int p)
  35. {
  36. 	p += 5;
  37. 	p = min(p, MX - 1);
  38. 	ll ans = 0;
  39. 	while (p)
  40. 	{
  41. 		ans += bit[b][p];
  42. 		p -= p & -p;
  43. 	}
  44. 	return ans;
  45. }
  46. void upd(int b, int p, ll v)
  47. {
  48. 	p += 5;
  49. 	p = max(1, p);
  50. 	while (p < MX)
  51. 	{
  52. 		bit[b][p] += v;
  53. 		p += p & -p;
  54. 	}
  55. }
  56.  
  57. ll readLow(int b, int p)
  58. {
  59. 	return read(b, p - 1);
  60. }
  61.  
  62. ll readHigh(int b, int p)
  63. {
  64. 	return read(b, INF) - read(b, p);
  65. }
  66.  
  67. int main()
  68. {
  69. 	rint(N);
  70. 	nrint(Q);
  71. 	ji(N) rint(arr[i]);
  72. 	ji(N) buf[i] = arr[i];
  73. 	sort(buf, buf + N);
  74. 	int idx = 0;
  75. 	ji(N)
  76. 	{
  77. 		if (i == 0 || buf[i] != buf[i-1])
  78. 			idxMap[buf[i]] = idx++;
  79. 	}
  80. 	ji(N) arr[i] = idxMap[arr[i]];
  81. 	ji(N)
  82. 	{
  83. 		memset(bit, 0, sizeof bit);
  84. 		ll ans = 0;
  85. 		upd(1, arr[i], 1);
  86. 		for (int j = i; j < N; j++)
  87. 		{
  88. 			answer[i][j] = readLow(4, arr[j]);
  89. 			upd(4, arr[j], readHigh(3, arr[j]));
  90. 			upd(3, arr[j], readLow(2, arr[j]));
  91. 			upd(2, arr[j], readHigh(1, arr[j]));
  92. 		}
  93. 	}
  94. 	jk(Q)
  95. 	{
  96. 		nrint(a); nrint(b);
  97. 		printf("%lld\n", answer[a-1][b-1]);
  98. 	}
  99. }
  100.  
Success #stdin #stdout 0s 34800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/j7Ee34
language:
C++14 (gcc 8.3)
created:
9 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!