提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114757	2023-10-24 07:42:27	Eug1ena	I	cpp	25/25	AC	197

//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr lint mod = 127237991;
#define all(x) begin(x), end(x)
#define bitcount(n) __builtin_popcountll((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzll(x))
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define rep2(i, l, r) for(int i = int(l); i < int(r); i++)
#define repr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define repr2(i, l, r) for(int i = int(r) - 1; i >= int(l); i--)
#define accumulate you cannot use this word!
constexpr int inf9 = 1e9; constexpr lint inf18 = 1e18;
inline void Yes(bool condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class itr> void array_output(itr start, itr goal){ for(auto i = start; i != goal; i++) cout << (i == start ? "" : " ") << (*i); cout << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(b) return gcd(b, a % b); else return a; }
template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b < a){ a = b; return 1; } return 0; }
inline int has(lint i, int j){ return (i >> j) & 1; }
int dy[4] = {1, 0, -1, 0}; int dx[4] = {0, 1, 0, -1};
bool is_inside(lint y, lint x, lint H, lint W){ return (0 <= y && y < H && 0 <= x && x < W); }

struct io_init {
    io_init() {
        cin.tie(nullptr); cout.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }
} io_init;

struct Modint{
    lint x;
    
    Modint(): x(0) {}
    Modint(lint x): x(x >= 0 || x % mod == 0 ? x % mod : mod - (-x) % mod) {}
    
    Modint operator +(Modint a){ return Modint(*this) += a; }
    Modint operator -(Modint a){ return Modint(*this) -= a; }
    Modint operator *(Modint a){ return Modint(*this) *= a; }
    Modint operator /(Modint a){ return Modint(*this) /= a; }
    
    Modint operator -(){ return Modint(0) - Modint(*this); }
    
    Modint& operator +=(Modint a){
        x += a.x;
        if(x >= mod) x -= mod;
        return *this;
    }
    
    Modint& operator -=(Modint a){
        if(x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    
    Modint& operator *=(Modint a){
        x = x * a.x % mod;
        return *this;
    }
    
    Modint& operator /=(Modint a){
        (*this) *= a.inv();
        return *this;
    }
    
    Modint inv(){
        return pow(mod - 2);
    }
    
    Modint pow(lint exp){
        Modint ans(1), powed = (*this);
        while(exp){
            if(exp % 2) ans *= powed;
            powed *= powed;
            exp /= 2;
        }
        return ans;
    }
    
    bool operator ==(Modint a){ return x == a.x; }
    bool operator !=(Modint a){ return x != a.x; }
};

ostream& operator <<(ostream& os, Modint a){
    os << a.x;
    return os;
}

istream &operator >>(istream &is, Modint& a){
    lint x;
    is >> x;
    a = Modint(x);
    return is;
}



int val[5][101010];

Modint dp[5][101010];
Modint sum[101010];
    
int main(){
    int n;
    cin >> n;
    rep(i, 5){
        rep(j, n){
            cin >> val[i][j];
        }
        sort(val[i], val[i] + n);
    }
    
    rep(i, n) dp[0][i] = 1;
    
    rep(i, 4){
        sum[0] = 0;
        rep(j, n){
            sum[j + 1] = sum[j] + dp[i][j];
        }
        
        rep(j, n){
            int L = int(lower_bound(val[i], val[i] + n, val[i + 1][j]) - val[i]);
            
            dp[i + 1][j] += sum[L];
        }
    }
    
    Modint ans = 0;
    rep(i, n){
        ans += dp[4][i];
    }
    cout << ans << endl;
}

sample1.txt AC 5
sample2.txt AC 8
sample3.txt AC 7
sample4.txt AC 10
sample5.txt AC 6
case1.txt AC 14
case2.txt AC 15
case3.txt AC 15
case4.txt AC 15
case5.txt AC 15
case6.txt AC 116
case7.txt AC 75
case8.txt AC 91
case9.txt AC 72
case10.txt AC 39
case11.txt AC 161
case12.txt AC 196
case13.txt AC 142
case14.txt AC 178
case15.txt AC 159
case16.txt AC 110
case17.txt AC 197
case18.txt AC 108
case19.txt AC 173
case20.txt AC 107
197 AC197 AC