Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Author: aksayushx
- **/
- #include<bits/stdc++.h>
- #define F first
- #define S second
- #define all(a) a.begin(),a.end()
- #define rall(a) a.rbegin(),a.rend()
- #define sz(x) (long long)x.size()
- #define uniq(a) a.erase(unique(all(a)),a.end())
- #define pb push_back
- #define mp make_pair
- #define mod 1'000'000'007
- #define MOD 998244353
- #define pi 3.141592653589793238462
- #define pll pair<ll,ll>
- #define pii pair<int,int>
- #define setp(x) fixed<<setprecision(x)
- #define deb(x) cerr<<#x<<"="<<x<< '\n'
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- ll power(ll x,ll y,ll m);
- ll modInverse(ll n,ll m);
- ll nCr(ll n,ll r,ll m);
- ll ceiling(ll x,ll y);
- const int block=700;
- const double eps=1e-9;
- const int rnd_mx=1e9;
- template <typename T>
- void read(vector<T>& a){
- for(T &e:a){
- cin>>e;
- }
- }
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- inline bool equal(ld x,ld y){
- return abs(x-y)<eps;
- }
- void add(int& a,int b){
- a+=b;
- if(a>=MOD) a-=MOD;
- }
- int lcm(int a,int b){
- return (a*b)/__gcd(a,b);
- }
- const int mx=3000;
- struct fenwick{
- int n;
- vector<int> bit;
- fenwick(int n){
- this->n=n;
- bit.assign(n,0);
- }
- int sum(int r){
- int s=0;
- for(;r>=0;r=(r&(r+1))-1){
- s=(s+bit[r])%mod;
- }
- return s;
- }
- void update(int idx,int del){
- for(;idx<n;idx=idx|(idx+1)){
- bit[idx]=(bit[idx]+del)%mod;
- }
- }
- };
- void aksayushx()
- {
- int n,m;
- cin>>n>>m;
- vector<int> a(n),b(m);
- read(a),read(b);
- auto ac=a;
- uniq(ac);
- sort(all(ac));
- int acs=ac.size();
- vector<vector<int>> dp(m,vector<int>(n,0));
- function<int(int)> idx=[&](int x){
- int idx=lower_bound(all(ac),x)-ac.begin();
- return idx;
- };
- fenwick ft(acs);
- for(int i=0;i<n;i++){
- dp[0][i]=1;
- }
- for(int i=1;i<m;i++){
- ft=fenwick(acs);
- for(int j=0;j<n;j++){
- int val=b[i]+a[j],xt=val-b[i-1];
- if(j>0) ft.update(idx(a[j-1]),dp[i-1][j-1]);
- if(xt<=0) continue;
- int id=upper_bound(all(ac),xt)-ac.begin();
- --id;
- if(id<0) continue;
- dp[i][j]=(dp[i][j]+ft.sum(id))%mod;
- }
- }
- int ans=0;
- for(int i=0;i<n;i++){
- ans+=dp[m-1][i];
- ans%=mod;
- }
- cout<<ans<<'\n';
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- #ifdef AKSAYUSHX
- (void)!freopen("input.txt","r",stdin);
- (void)!freopen("output.txt","w",stdout);
- (void)!freopen("error.txt","w",stderr);
- #endif
- int t=1,x=1;
- //cin>>t;
- while(t--)
- {
- //cout<<"Case #"<<x++<<": ";
- aksayushx();
- }
- return 0;
- }
- // Returns x raised to the power y modulo mod
- ll power(ll x, ll y, ll m=mod)
- {
- ll res = 1;
- x = x % m;
- if (x == 0) return 0;
- while (y > 0)
- {
- if (y & 1)
- res = (res*x) % m;
- y = y>>1;
- x = (x*x) % m;
- }
- return res;
- }
- ll modInverse(ll n,ll m=mod)
- {
- return power(n, m-2,m);
- }
- ll ceiling(ll x,ll y)
- {
- return (x+y-1)/y;
- }
- /*
- ll nCr(ll n,ll r,ll m=mod)
- {
- if(r==0) return 1;
- //return (fac[n] * minv[r] % m * minv[n - r] % m) % m;
- return (fac[n] * modInverse(fac[r],m) % m * modInverse(fac[n - r],m) % m) % m;
- }*/
Advertisement
Add Comment
Please, Sign In to add comment