General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
148661424 Practice:
Satish_S
1649E - 54 GNU C++17 Time limit exceeded on test 9 2000 ms 9560 KB 2022-03-07 07:57:11 2022-03-07 07:57:11
 
 
→ Source
/* author satMAN GOD */
#include "bits/stdc++.h"
using namespace                        std;
#define int                            long long
#define pi                             pair<int,int>
#define pq                             priority_queue
#define For(it,x)                      for(auto it=(x).begin();it!=(x).end();it++)
#define rFor(it,x)                     for(auto it=(x).rbegin();it!=(x).rend();it++)
#define endl                           '\n'
#define  min_pq(T)                     pq<T,vector<T>,greater<T>>
#define  max_pq(T)                     pq<T,vector<T>>
#define op(mp)                         mp.reserve(1024); mp.max_load_factor(0.25);
#define all(x)                         x.begin(),x.end()
#define rall(x)                        x.rbegin(),x.rend()
#define reset(x,val)                   memset(x,val,sizeof(x));
#define found(mp,x)                    mp.find(x)!=mp.end()
#define foundp(mp,i,j)                 mp.find({i,j})!=mp.end()
#define del(mp,val)                    if(mp[val]<=0)mp.erase(val);
#define gcd(a,b)                       __gcd(a,b)
int lcm(int a,int b)                   {return (a*b)/gcd(a,b);}
template<typename T>                   T min(T a,T b,T c)                              {return min(a,min(b,c));}
template<typename T>                   T max(T a,T b,T c)                              {return max(a,max(b,c));}
template<typename T>                   T max(T a,T b,T c,T d)                          {return max(a,max(b,max(c,d)));}
template<typename T>                   T min(T a,T b,T c,T d)                          {return min(a,min(b,min(c,d)));}
template<typename t1>                  void fill(vector<t1>&arr,t1 val)                {for(int i=0;i<(int)arr.size();i++)arr[i]=val;}
template<typename t1>                  void fill(vector<vector<t1>>&arr,t1 val)        {for(int i=0;i<(int)arr.size();i++){for(int j=0;j<(int)arr[i].size();j++)     arr[i][j]=val;}}
template<typename T>                   void read(vector<T>&arr,int N)                  {arr.clear(); arr.resize(N);for(int i=0;i<N;i++)cin>>arr[i];}
template<typename T>                   void read(vector<pair<T,T>>&arr,int N)          {arr.clear();arr.resize(N);for(int i=0;i<(int)arr.size();i++)cin>>arr[i].first>>arr[i].second;}
template<typename T>                   void read(vector<vector<T>>&arr,int N,int M)    {arr.clear();arr.resize(N,vector<T>(M));for(int i=0;i<N;i++){for(int j=0;j<M;j++)cin>>arr[i][j];}}

#define _print(x)                       cout<<(#x)<<endl;print(x);
void print(int t)                      {cout << t;}
void print(string t)                   {cout << t;}
void print(char t)                     {cout << t;}
void print(double t)                   {cout << t;}
template<typename T1,typename T2>
void print(pair<T1,T2>&p)              {cout<<"{";print(p.first);cout<<",";print(p.second);cout<<"}";}
template<class T>
void print(vector<T>&arr)              {cout<<"(";for(auto it:arr)cout<<it<<' ';cout<<")";cout<<endl;}
template<typename T1,typename T2>
void print(vector<pair<T1,T2>>&arr)    {cout<<"(";for(auto it:arr)print(it);cout<<")";cout<<endl;}
template<typename T>
void print(vector<vector<T>>&arr)      {for(auto it:arr) { print(it); }cout<<endl;}
template<typename T1>
void print(set<T1>&ss)                 {cout<<"{";for(auto it:ss) { print(it);cout<<','; }cout<<"}"<<endl;}
template<typename T1,typename T2>
void print(map<T1,T2>&mp)              {For(it,mp){print(it->first);cout<<" -> ";print(it->second);cout<<endl;}cout<<endl;}



const int mod=998244353;

int power(int a,int b)                 {int res=1;while(b>0){if(b&1)res*=a;a=a*a;b=b>>1;}return res;}
int fastpow(int a,int p)               {int res=1;while(p){if(p%2==0){a=(a*a)%mod; p=p/2; }else{res=(res*a)%mod; p--; } }return res;}

const int Max=1e17 , Min=-1e17 ;

int mod_add(int a,int b)               { a=a%mod; b=b%mod; int res=((a+b)%mod+mod)%mod;return res;}
int mod_sub(int a,int b)               { a=a%mod; b=b%mod; int res=((a-b)%mod+mod)%mod;return res;}
int mod_mul(int a,int b)               { a=a%mod; b=b%mod; int res=((a*b)%mod+mod)%mod;return res;}
int mod_div(int a,int b)               { a=a%mod; b=b%mod; int res=(mod_mul(a,fastpow(b,mod-2))+mod)%mod;return res;}
int ceil   (int a,int b)               { int ret=a/b+(a%b!=0);return ret;}

int N,M,K,Q;
const int P=31;

/*☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻ (>‿◠)✌ ☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻☻*/

const int nax=2*1e5+5;
vector<int>make;
vector<int>dis(nax,0);
vector<int>arr;
vector<int>brr;
vector<int>fact;


void build(int ind,int l,int r){
    if(l==r){


        make[ind]=dis[l];
        return;
    }
    int m=(l+r)/2;
    build(2*ind+1,l,m);
    build(2*ind+2,m+1,r);
    make[ind]=make[2*ind+1]+make[2*ind+2];
}
int get(int ind,int l,int r,int L,int R){
    if(l>R || r<L)
        return 0;
    if(L<=l and r<=R)
        return make[ind];

    int m=(l+r)/2;
    return get(2*ind+1,l,m,L,R)+get(2*ind+2,m+1,r,L,R);
}
void update(int ind,int l,int r,int index){
    if(l==r){

        make[ind]=dis[l];
        return;
    }
    int m=(l+r)/2;
    if(index<=m)
        build(2*ind+1,l,m);
    else
        build(2*ind+2,m+1,r);

    make[ind]=make[2*ind+1]+make[2*ind+2];

}


void run(){
    fact.resize(nax);
    fact[0]=1;
    for(int i=1;i<nax;i++)
        fact[i]=mod_mul(fact[i-1],i);
}

void solve(){
    run();
    cin>>N>>M;
    read(arr,N);
    read(brr,M);

    for(int i=0;i<N;i++)
        dis[arr[i]]++;



    make.resize(4*nax);
    build(0,0,nax-1);


    int D=1;
    for(int i=0;i<nax;i++)
        D=mod_mul(D,fact[dis[i]]);

    int ans=0;
    for(int i=0;i<max(N,M);i++){
        if(i>=min(N,M) and N<M){
            ans=mod_add(ans,1);
            break;
        }
        else if(i>=min(N,M))
            break;

        int tot=fact[N-i -1];
        tot=mod_div(tot,D);
        int G=get(0,0,nax-1,1,brr[i]-1);

       // cout<<arr[i]<<' '<<tot<<' '<<G<<' ';
        tot=mod_mul(tot,G);
      //  cout<<tot<<endl;
        ans=mod_add(ans,tot);


        if(dis[brr[i]]==0)
            break;
        D=mod_div(D,dis[brr[i]]);
        dis[brr[i]]--;
        update(0,0,nax-1,brr[i]);

    }
    cout<<ans<<endl;

}

signed main(){

    bool testcases = false      ;
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    if(testcases)                     {int tt; cin>>tt; while(tt--) solve();}
    else                               solve();

}


 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details