QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#484424#8712. Flooding WallWansur0 1ms8068kbC++239.5kb2024-07-19 18:40:052024-07-19 18:40:06

Judging History

This is the latest submission verdict.

  • [2024-07-19 18:40:06]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 8068kb
  • [2024-07-19 18:40:05]
  • Submitted

answer

#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

using namespace std;

template <typename T>
T inverse(T a, T m) {
    T u = 0, v = 1;
    while (a != 0) {
        T t = m / a;
        m -= t * a; swap(a, m);
        u -= t * v; swap(u, v);
    }
    assert(m == 1);
    return u;
}

template <typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;

    constexpr Modular() : value() {}
    template <typename U>
    Modular(const U& x) {
        value = normalize(x);
    }

    template <typename U>
    static Type normalize(const U& x) {
        Type v;
        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
        else v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
    }

    const Type& operator()() const { return value; }
    template <typename U>
    explicit operator U() const { return static_cast<U>(value); }
    constexpr static Type mod() { return T::value; }

    Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
    template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) { Modular result(*this); *this += 1; return result; }
    Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
    Modular operator-() const { return Modular(-value); }

    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
        return *this;
    }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
        long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
    template <typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }

    Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

    friend const Type& abs(const Modular& x) { return x.value; }

    template <typename U>
    friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

    template <typename U>
    friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

    template <typename V, typename U>
    friend V& operator>>(V& stream, Modular<U>& number);

private:
    Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
    return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
    return to_string(number());
}

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
    return stream << number();
}

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
    typename common_type<typename Modular<T>::Type, long long>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}

// using ModType = int;

// struct VarMod { static ModType value; };
// ModType VarMod::value;
// ModType& md = VarMod::value;
// using Mint = Modular<VarMod>;

const int md = (int)1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
#define int long long

typedef long long ll;
const int maxn = 5e5 + 12;
const int mod = 1e9 + 7;

Mint nsum[maxn];
Mint ndp[maxn];
Mint sum[maxn];
Mint dp[maxn];
Mint cla[maxn], clb[maxn];
Mint sla[maxn], slb[maxn];
int a[maxn];
int b[maxn];
int n, m, s;

void solve(){
    cin >> n;
    vector<int> t;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        t.push_back(a[i]);
    }
    for(int i=1;i<=n;i++) {
        cin >> b[i];
        t.push_back(b[i]);
    }
    m = t.size();
    sort(t.begin(), t.end());
    t.resize(unique(t.begin(), t.end()) - t.begin());
    for(int i=1;i<=n;i++){
        a[i] = lower_bound(t.begin(), t.end(), a[i]) - t.begin() + 1;
        b[i] = lower_bound(t.begin(), t.end(), b[i]) - t.begin() + 1;
    }
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        for(int x=0;x<=m;x++){
            if(a[i] >= x){
                ndp[a[i]] += dp[x];
                nsum[a[i]] += sum[x];
                if(a[i] > x){
                    cla[i] += dp[x];
                    sla[i] += sum[x];
                }
            }
            else{
                ndp[x] += dp[x];
                nsum[x] += sum[x] + dp[x] * (x - a[i]);
            }
            if(b[i] >= x){
                ndp[b[i]] += dp[x];
                nsum[b[i]] += sum[x];
                if(b[i] > x){
                    clb[i] += dp[x];
                    slb[i] += sum[x];
                }
            }
            else{
                ndp[x] += dp[x];
                nsum[x] += sum[x] + dp[x] * (x - b[i]);
            }
        }
        for(int x=0;x<=m;x++){
            dp[x] = ndp[x];
            sum[x] = nsum[x];
            ndp[x] = nsum[x] = 0;
        }
    }
    for(int x=0;x<=m;x++){
        dp[x] = sum[x] = 0;
    }
    dp[0] = 1;
    Mint ans = 0;
    for(int i=n;i;i--){
        Mint cra = 0, crb = 0, sra = 0, srb = 0;
        for(int x=0;x<=m;x++){
            if(a[i] >= x){
                ndp[a[i]] += dp[x];
                nsum[a[i]] += sum[x];
                cra += dp[x];
                sra += sum[x];
            }
            else{
                ndp[x] += dp[x];
                nsum[x] += sum[x] + dp[x] * (x - a[i]);
            }
            if(b[i] >= x){
                ndp[b[i]] += dp[x];
                nsum[b[i]] += sum[x];
                crb += dp[x];
                srb += sum[x];
            }
            else{
                ndp[x] += dp[x];
                nsum[x] += sum[x] + dp[x] * (x - b[i]);
            }
        }
        for(int x=0;x<=m;x++){
            dp[x] = ndp[x];
            sum[x] = nsum[x];
            ndp[x] = nsum[x] = 0;
        }
        ans += cla[i] * sra + sla[i] * cra;
        ans += clb[i] * srb + slb[i] * crb;
    }
    cout << ans << ent;
}

signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 1ms
memory: 7820kb

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 7808kb

input:

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

output:

21116

result:

ok single line: '21116'

Test #3:

score: 0
Accepted
time: 0ms
memory: 7808kb

input:

1
1
2

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1ms
memory: 7844kb

input:

2
1 1
2 2

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 7808kb

input:

3
1 1 1
2 2 2

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 1ms
memory: 8040kb

input:

3
1 1 1
3 2 3

output:

3

result:

ok single line: '3'

Test #7:

score: 0
Accepted
time: 1ms
memory: 8068kb

input:

3
2 1 1
3 2 3

output:

4

result:

ok single line: '4'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7804kb

input:

3
1 1 2
3 2 3

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 0ms
memory: 7808kb

input:

4
1 1 2 2
2 2 1 1

output:

6

result:

ok single line: '6'

Test #10:

score: -8
Wrong Answer
time: 1ms
memory: 8052kb

input:

3
1 4 4
3 1 1

output:

1

result:

wrong answer 1st lines differ - expected: '2', found: '1'

Subtask #2:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 1ms
memory: 7988kb

input:

100
948 425 211 688 416 81 356 602 712 954 117 522 797 75 281 491 662 669 78 156 939 526 929 937 916 619 166 777 48 898 449 278 298 714 668 755 679 38 389 602 195 135 672 833 655 541 473 27 596 274 351 353 598 993 837 246 950 99 179 751 481 843 550 195 964 279 806 82 330 599 124 756 649 838 513 625 ...

output:

316868564

result:

wrong answer 1st lines differ - expected: '164439470', found: '316868564'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Runtime Error

Test #57:

score: 0
Runtime Error

input:

500000
1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 1...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%