QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#484400#8712. Flooding WallWansur12 56ms42928kbC++239.1kb2024-07-19 18:19:002024-07-19 18:19:00

Judging History

This is the latest submission verdict.

  • [2024-07-19 18:19:00]
  • Judged
  • Verdict: 12
  • Time: 56ms
  • Memory: 42928kb
  • [2024-07-19 18:19:00]
  • 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 sums[maxn][4];
Mint dps[maxn][4];
Mint sum[maxn][4];
Mint dp[maxn][4];
int a[maxn];
int b[maxn];
int n, m, s;

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=n;i++) {
        cin >> b[i];
    }
    dp[0][0] = 1;
    sum[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int x=0;x<=2;x++){
            if(a[i] >= x){
                dp[i][a[i]] += dp[i-1][x];
                sum[i][a[i]] += sum[i-1][x];
            }
            else{
                dp[i][x] += dp[i-1][x];
                sum[i][x] += sum[i-1][x] + dp[i-1][x] * (x - a[i]);
            }
            if(b[i] >= x){
                dp[i][b[i]] += dp[i-1][x];
                sum[i][b[i]] += sum[i-1][x];
            }
            else{
                dp[i][x] += dp[i-1][x];
                sum[i][x] += sum[i-1][x] + dp[i-1][x] * (x - b[i]);
            }
        }
    }
    dps[n+1][0] = 1;
    for(int i=n;i;i--){
        for(int x=0;x<=2;x++){
            if(a[i] >= x){
                dps[i][a[i]] += dps[i+1][x];
                sums[i][a[i]] += sums[i+1][x];
            }
            else{
                dps[i][x] += dps[i+1][x];
                sums[i][x] += sums[i+1][x] + dps[i+1][x] * (x - a[i]);
            }
            if(b[i] >= x){
                dps[i][b[i]] += dps[i+1][x];
                sums[i][b[i]] += sums[i+1][x];
            }
            else{
                dps[i][x] += dps[i+1][x];
                sums[i][x] += sums[i+1][x] + dps[i+1][x] * (x - b[i]);
            }
        }
    }
    Mint ans = 0;
    for(int i=1;i<=n;i++){
        Mint cntl = 0, sl = 0, cntr = 0, sr = 0;
        for(int x=0;x<=a[i];x++){
            cntr += dps[i+1][x];
            sr += sums[i+1][x];
            if(x == a[i]) break;
            cntl += dp[i-1][x];
            sl += sum[i-1][x];
        }
        ans += sr * cntl + sl * cntr;
    }
    for(int i=1;i<=n;i++){
        Mint cntl = 0, sl = 0, cntr = 0, sr = 0;
        for(int x=0;x<=b[i];x++){
            cntr += dps[i+1][x];
            sr += sums[i+1][x];
            if(x == b[i]) break;
            cntl += dp[i-1][x];
            sl += sum[i-1][x];
        }
        ans += sr * cntl + sl * cntr;
    }
    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();
    }
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

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

input:

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

output:

6

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #23:

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

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:

0

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 12
Accepted

Test #57:

score: 12
Accepted
time: 42ms
memory: 42736kb

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:

869044223

result:

ok single line: '869044223'

Test #58:

score: 0
Accepted
time: 56ms
memory: 42732kb

input:

499993
1 1 2 1 1 2 1 1 2 1 1 1 2 2 2 2 1 1 1 2 1 1 1 2 2 2 1 1 2 2 1 2 1 2 1 2 1 2 2 2 2 1 1 2 1 2 1 2 2 1 1 2 2 2 2 2 1 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 1 1 2 1 1 2 1 1 1 1 2 1 1 1 2 2 1 1 2 1 1 1 2 2 2 2 1 1 2 1 2 1 2 2 1 2 1 1 1 1 2 1 1 2 1 2 2 1 2 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 2 1 1 1...

output:

480826834

result:

ok single line: '480826834'

Test #59:

score: 0
Accepted
time: 54ms
memory: 42928kb

input:

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

output:

869044223

result:

ok single line: '869044223'

Test #60:

score: 0
Accepted
time: 39ms
memory: 42736kb

input:

499999
2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 1 1 2 2 2 1 1 1 2 2 2 2 2 1 2 2 1 1 2 2 2 2 1 1 2 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 1 2 1 1 2 1 2 1 1 2 1 1 1 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1 1 1 2 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1...

output:

192864306

result:

ok single line: '192864306'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%