fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  4.  
  5. #define fi first
  6. #define se second
  7.  
  8. #define For(i, a, b) for (int i = a; i <= b; i++)
  9. #define ForRL(i, a, b) for (int i = a; i >= b; i--)
  10. #define rep(i, n) for (int i = 0; i < n; i++)
  11. #define repRL(i, n) for (int i = (n) - 1; i >= 0; i--)
  12. #define pb push_back
  13. #define coutE(x) {cout << x; exit(0);}
  14. #define cinStr(x, n) cin >> x; x = ' ' + x; n = x.size() - 1;
  15.  
  16. #define Bitcnt(x) __builtin_popcount(x)
  17. #define all(x) x.begin(), x.end()
  18. #define bs binary_search
  19. #define ub upper_bound
  20. #define lb lower_bound
  21. #define endl '\n'
  22.  
  23. #define ll long long
  24. #define ii pair<int, int>
  25. #define vi vector<int>
  26. #define vii vector<ii>
  27.  
  28. using namespace std;
  29.  
  30. const int N = 1e5 + 5;
  31.  
  32. const int MOD = 1e9 + 7;
  33. const int INF = 1e9;
  34. const long long LINF = 1e18;
  35.  
  36. const int B = 320;
  37.  
  38. const int dx[] = {1, 0, 0, -1};
  39. const int dy[] = {0, 1, -1, 0};
  40.  
  41. mt19937_64 rng(time(0));
  42.  
  43. void file(string s){
  44.  
  45.     if (s.empty()) return;
  46.  
  47.     freopen((s + ".inp").c_str(), "r", stdin);
  48.     freopen((s + ".out").c_str(), "w", stdout);
  49. }
  50.  
  51. struct query{
  52. 	int l, r, t, i;
  53.  
  54. 	bool operator < (query &q){
  55. 		if (l/B != q.l/B) return l/B < q.l/B;
  56. 		return r < q.r;
  57. 	}
  58. };
  59.  
  60. int n, q, a[N];
  61. int x, y, cur;
  62. int ans[N];
  63. int sumB[B + 5], cntB[B + 5], cnt[B + 5][B + 5];
  64. vector<query> quer;
  65.  
  66. void add(int x){
  67.  
  68. 	int block = x/B;
  69. 	sumB[block] += x; cntB[block]++;
  70. 	cnt[block][x % B]++;
  71. }
  72.  
  73. void remove(int x){
  74.  
  75. 	int block = x/B;
  76. 	sumB[block] -= x; cntB[block]--;
  77. 	cnt[block][x % B]--;
  78. }
  79.  
  80. void MO(query Q){
  81.  
  82. 	int l = Q.l, r = Q.r, t = Q.t, i = Q.i;
  83.  
  84. 	while (l < x) add(a[--x]);
  85. 	while (y < r) add(a[++y]);
  86. 	while (x < l) remove(a[x++]);
  87. 	while (r < y) remove(a[y--]);
  88.  
  89. 	int res = 0;
  90. 	For(block, 0, B){
  91.  
  92. 		if (t >= sumB[block]) t -= sumB[block], res += cntB[block];
  93. 		else{
  94. 			rep(tmp, B){
  95.  
  96. 				int val = block * B + tmp;
  97. 				if (!val || val > t) continue;
  98.  
  99. 				int v = min(cnt[block][tmp], t/val);
  100.  
  101. 				res += v;
  102. 				t -= v * val;
  103. 			}
  104.  
  105. 			break;
  106. 		}
  107. 	}
  108.  
  109. 	ans[i] = res;
  110. }
  111.  
  112. void solve(){
  113.  
  114. 	cin >> n >> q;
  115. 	For(i, 1, n) cin >> a[i];
  116.  
  117. 	rep(i, q){
  118. 		int l, r, t; cin >> l >> r >> t;
  119. 		quer.pb({l, r, t, i});
  120. 	}
  121.  
  122. 	sort(all(quer));
  123.  
  124. 	x = quer[0].l, y = quer[0].l - 1;
  125. 	for (query Q: quer) MO(Q);
  126.  
  127. 	rep(i, q) cout << ans[i] << endl;
  128. }
  129.  
  130.  
  131. signed main(){
  132.  
  133. 	fastIO; file("");
  134.  
  135. 	solve();
  136.  
  137. 	return 0;
  138. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5 3
2 3 4 5 6
1 2 4
2 4 13
3 3 1
stdout
copy 
1
3
0
https://ideone.com/ykyAkj
language:
C++14 (gcc 8.3)
created:
14 days 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!