Guest User

Untitled

a guest
Oct 25th, 2022
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.58 KB | None | 0 0
  1. /**
  2. * Author: aksayushx
  3. **/
  4. #include<bits/stdc++.h>
  5. #define F first
  6. #define S second
  7. #define all(a) a.begin(),a.end()
  8. #define rall(a) a.rbegin(),a.rend()
  9. #define sz(x) (long long)x.size()
  10. #define uniq(a) a.erase(unique(all(a)),a.end())
  11. #define pb push_back
  12. #define mp make_pair
  13. #define mod 1'000'000'007
  14. #define MOD 998244353
  15. #define pi 3.141592653589793238462
  16. #define pll pair<ll,ll>
  17. #define pii pair<int,int>
  18. #define setp(x) fixed<<setprecision(x)
  19. #define deb(x) cerr<<#x<<"="<<x<< '\n'
  20. using namespace std;
  21. typedef long long ll;
  22. typedef long double ld;
  23.  
  24.  
  25.  
  26. ll power(ll x,ll y,ll m);
  27. ll modInverse(ll n,ll m);
  28. ll nCr(ll n,ll r,ll m);
  29. ll ceiling(ll x,ll y);
  30.  
  31. const int block=700;
  32. const double eps=1e-9;
  33. const int rnd_mx=1e9;
  34.  
  35. template <typename T>
  36. void read(vector<T>& a){
  37. for(T &e:a){
  38. cin>>e;
  39. }
  40. }
  41.  
  42. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  43.  
  44. inline bool equal(ld x,ld y){
  45. return abs(x-y)<eps;
  46. }
  47.  
  48.  
  49. void add(int& a,int b){
  50. a+=b;
  51. if(a>=MOD) a-=MOD;
  52. }
  53.  
  54. int lcm(int a,int b){
  55. return (a*b)/__gcd(a,b);
  56. }
  57.  
  58.  
  59. const int mx=3000;
  60.  
  61. struct fenwick{
  62. int n;
  63. vector<int> bit;
  64. fenwick(int n){
  65. this->n=n;
  66. bit.assign(n,0);
  67. }
  68. int sum(int r){
  69. int s=0;
  70. for(;r>=0;r=(r&(r+1))-1){
  71. s=(s+bit[r])%mod;
  72. }
  73. return s;
  74. }
  75. void update(int idx,int del){
  76. for(;idx<n;idx=idx|(idx+1)){
  77. bit[idx]=(bit[idx]+del)%mod;
  78. }
  79. }
  80. };
  81.  
  82.  
  83. void aksayushx()
  84. {
  85. int n,m;
  86. cin>>n>>m;
  87. vector<int> a(n),b(m);
  88. read(a),read(b);
  89. auto ac=a;
  90. uniq(ac);
  91. sort(all(ac));
  92. int acs=ac.size();
  93. vector<vector<int>> dp(m,vector<int>(n,0));
  94.  
  95. function<int(int)> idx=[&](int x){
  96. int idx=lower_bound(all(ac),x)-ac.begin();
  97. return idx;
  98. };
  99.  
  100. fenwick ft(acs);
  101.  
  102. for(int i=0;i<n;i++){
  103. dp[0][i]=1;
  104. }
  105.  
  106. for(int i=1;i<m;i++){
  107. ft=fenwick(acs);
  108. for(int j=0;j<n;j++){
  109. int val=b[i]+a[j],xt=val-b[i-1];
  110.  
  111. if(j>0) ft.update(idx(a[j-1]),dp[i-1][j-1]);
  112.  
  113. if(xt<=0) continue;
  114. int id=upper_bound(all(ac),xt)-ac.begin();
  115.  
  116. --id;
  117. if(id<0) continue;
  118. dp[i][j]=(dp[i][j]+ft.sum(id))%mod;
  119. }
  120. }
  121. int ans=0;
  122. for(int i=0;i<n;i++){
  123. ans+=dp[m-1][i];
  124. ans%=mod;
  125. }
  126. cout<<ans<<'\n';
  127. }
  128.  
  129.  
  130. int main()
  131. {
  132. ios_base::sync_with_stdio(false);
  133. cin.tie(NULL);
  134. cout.tie(NULL);
  135. #ifdef AKSAYUSHX
  136. (void)!freopen("input.txt","r",stdin);
  137. (void)!freopen("output.txt","w",stdout);
  138. (void)!freopen("error.txt","w",stderr);
  139. #endif
  140. int t=1,x=1;
  141. //cin>>t;
  142. while(t--)
  143. {
  144. //cout<<"Case #"<<x++<<": ";
  145. aksayushx();
  146. }
  147. return 0;
  148. }
  149.  
  150.  
  151. // Returns x raised to the power y modulo mod
  152. ll power(ll x, ll y, ll m=mod)
  153. {
  154. ll res = 1;
  155. x = x % m;
  156. if (x == 0) return 0;
  157. while (y > 0)
  158. {
  159. if (y & 1)
  160. res = (res*x) % m;
  161. y = y>>1;
  162. x = (x*x) % m;
  163. }
  164. return res;
  165. }
  166.  
  167. ll modInverse(ll n,ll m=mod)
  168. {
  169. return power(n, m-2,m);
  170. }
  171.  
  172. ll ceiling(ll x,ll y)
  173. {
  174. return (x+y-1)/y;
  175. }
  176.  
  177. /*
  178. ll nCr(ll n,ll r,ll m=mod)
  179. {
  180. if(r==0) return 1;
  181. //return (fac[n] * minv[r] % m * minv[n - r] % m) % m;
  182. return (fac[n] * modInverse(fac[r],m) % m * modInverse(fac[n - r],m) % m) % m;
  183. }*/
  184.  
Advertisement
Add Comment
Please, Sign In to add comment