fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define sz(a) (int)a.size()
  6. #define all(a) begin(a),end(a)
  7.  
  8. using vi = vector<int>;
  9.  
  10. const int mxN = (int)3e4+10;
  11. const int MOD = (int)1e9+7;
  12. const int B = 175;
  13.  
  14. int n, q, dp[110];
  15. int a[mxN], l[mxN], r[mxN], x[mxN], ans[mxN];
  16.  
  17. void add(int x){
  18. 	x = a[x];
  19. 	for(int i = x; i <= 100; i++)
  20. 		dp[i]+=dp[i-x], dp[i]%=MOD;
  21. }
  22.  
  23. void rem(int x){
  24. 	x = a[x];
  25. 	for(int i = 100; i >= x; i--)
  26. 		dp[i]+=MOD-dp[i-x], dp[i]%=MOD;
  27. }
  28.  
  29. int main(){
  30.     ios_base::sync_with_stdio(false); cin.tie(0);
  31.     cin >> n >> q; dp[0] = 1;
  32.     for(int i = 1; i <= n; i++) cin >> a[i];
  33.     for(int i = 1; i <= q; i++) 
  34. 		cin >> l[i] >> r[i] >> x[i];
  35.     vi v(q,0); iota(all(v),1);
  36.     sort(all(v),[&](int i, int j){
  37. 		if(l[i]/B==l[j]/B) return (l[i]/B)%2?r[i]>r[j]:r[i]<r[j];
  38. 		return l[i]<l[j];
  39. 	});
  40. 	int L = 1, R = 0;
  41. 	for(auto i : v){
  42. 		while(R<r[i]) add(++R);
  43. 		while(L>l[i]) add(--L);
  44. 		while(L<l[i]) rem(L++);
  45. 		while(R>r[i]) rem(R--);
  46. 		ans[i] = dp[x[i]];
  47. 	}
  48. 	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
  49. }
  50.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 2
1 2 3 4 5
1 3 2
3 5 1
stdout
copy 
2
0
https://ideone.com/2F5FfU
language:
C++14 (gcc 8.3)
created:
4 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!