Submission #701517

#	Time	Username	Problem	Language	Result	Execution time	Memory
701517		Cyanmond	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	189 ms	15360 KiB

fancyfence

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 mod = 1000000007;

i64 add(i64 a, i64 b) {
    return (a + b) % mod;
}
i64 sub(i64 a, i64 b) {
    return (a + mod - b) % mod;
}
i64 mul(i64 a, i64 b) {
    return (a * b) % mod;
}
void eadd(i64 &a, i64 b) {
    a = add(a, b);
}
void esub(i64 &a, i64 b) {
    a = sub(a, b);
}
void emul(i64 &a, i64 b) {
    a = mul(a, b);
}

i64 calcPaint(i64 x, i64 y) {
    return mul((1 + x) * x / 2 % mod, (1 + y) * y / 2 % mod);
}

int main() {
    int N;
    std::cin >> N;
    std::vector<std::pair<i64, i64>> P(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i].first;
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i].second;
    }
    std::vector<i64> rW(N + 1);
    for (int i = 0; i < N; ++i) {
        rW[i + 1] = rW[i] + P[i].second;
    }
    auto calcRangeWidth = [&](const int l, const int r) {
        return rW[r] - rW[l];
    };
    
    std::map<i64, std::vector<i64>> eV;
    for (int i = 0; i < N; ++i) {
        eV[P[i].first].push_back(i);
    }
    std::set<std::tuple<i64, i64, i64>> rangeS; // (first, length)
    rangeS.insert({0, calcRangeWidth(0, N), 0});
    i64 answer = 0;
    for (const auto &[h, vec] : eV) {
        for (const int i : vec) {
            const auto p = calcRangeWidth(0, i);
            auto itr = rangeS.lower_bound({p + 1, 0, 0});
            assert(itr != rangeS.begin());
            --itr;
            
            // eval
            const auto [l, width, mh] = *itr;
            i64 a = calcPaint(h % mod, width % mod), b = calcPaint(mh % mod, width % mod);
            esub(a, b);
            eadd(answer, a);

            rangeS.erase(itr);
            i64 lw = p - l, rw = (l + width) - (p + P[i].second);
            if (lw != 0) {
                rangeS.insert({l, lw, h});
            }
            if (rw != 0) {
                rangeS.insert({p + P[i].second, rw, h});
            }
        }
    }
    std::cout << answer << std::endl;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27