QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#484428	#8712. Flooding Wall	Wansur	0	2ms	12316kb	C++23	9.4kb	2024-07-19 18:41:35	2024-07-19 18:41:35

Judging History

This is the latest submission verdict.

[2024-07-19 18:41:35]
Judged

Verdict: 0
Time: 2ms
Memory: 12316kb

Show

[2024-07-19 18:41:35]
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[10040][1040];
Mint dps[10040][1040];
Mint sum[10400][1040];
Mint dp[10040][1040];
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][0] = 1;
    sum[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int x=0;x<=1000;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<=1000;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();
    }
}

源文件, 语言: C++23

詳細信息

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 8

Accepted

time: 0ms

memory: 11916kb

input:

4
1 1 1 1
2 2 2 2

output:

result:

ok single line: '6'

Test #2:

score: 0

Accepted

time: 2ms

memory: 11948kb

input:

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

output:

result:

ok single line: '21116'

Test #3:

score: 0

Accepted

time: 1ms

memory: 11904kb

input:

1
1
2

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 1ms

memory: 12176kb

input:

2
1 1
2 2

output:

result:

ok single line: '0'

Test #5:

score: 0

Accepted

time: 1ms

memory: 11912kb

input:

3
1 1 1
2 2 2

output:

result:

ok single line: '1'

Test #6:

score: 0

Accepted

time: 1ms

memory: 12144kb

input:

3
1 1 1
3 2 3

output:

result:

ok single line: '3'

Test #7:

score: 0

Accepted

time: 1ms

memory: 12172kb

input:

3
2 1 1
3 2 3

output:

result:

ok single line: '4'

Test #8:

score: 0

Accepted

time: 0ms

memory: 11864kb

input:

3
1 1 2
3 2 3

output:

result:

ok single line: '4'

Test #9:

score: 0

Accepted

time: 0ms

memory: 11892kb

input:

4
1 1 2 2
2 2 1 1

output:

result:

ok single line: '6'

Test #10:

score: -8

Wrong Answer

time: 1ms

memory: 11912kb

input:

3
1 4 4
3 1 1

output:

result:

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

Subtask #2:

score: 0

Wrong Answer

Test #23:

score: 0

Wrong Answer

time: 0ms

memory: 12316kb

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:

Subtask #4:

score: 0

Skipped

Dependency #1:

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...

QOJ.ac

QOJ

Judging History

answer

詳細信息

Subtask #1:

Test #1:

input:

output:

result:

Test #2:

input:

output:

result:

Test #3:

input:

output:

result:

Test #4:

input:

output:

result:

Test #5:

input:

output:

result:

Test #6:

input:

output:

result:

Test #7:

input:

output:

result:

Test #8:

input:

output:

result:

Test #9:

input:

output:

result:

Test #10:

input:

output:

result:

Subtask #2:

Test #23:

input:

output:

result:

Subtask #3:

Dependency #2:

Subtask #4:

Dependency #1:

Subtask #5:

Test #57:

input:

output:

result:

Subtask #6:

Dependency #1: