Submission #528283

#	Time	Username	Problem	Language	Result	Execution time	Memory
528283		Olympia	Fancy Fence (CEOI20_fancyfence)	C++17	30 / 100	1069 ms	4328 KiB

fancyfence

#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#include <stack>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
using namespace std;
int M = 1e9 + 7;
struct modint {
    modint() : n(0) {}

    template<class T>
    modint(T n) {
        n %= M;
        if (n < 0) n += M;
        this->n = n;
    }

    modint &operator+=(const modint &r) {
        n += r.n;
        if (n >= M) n -= M;
        return *this;
    }

    modint &operator-=(const modint &r) {
        n -= r.n;
        if (n < 0) n += M;
        return *this;
    }

    modint &operator*=(const modint &r) {
        n = (int) ((long long) n * r.n % M);
        return *this;
    }

    modint &operator--() {
        if (--n == -1) n = M - 1;
        return *this;
    }

    modint &operator++() {
        if (++n == M) n = 0;
        return *this;
    }

    modint operator--(int) {
        modint t = *this;
        --*this;
        return t;
    }

    modint operator++(int) {
        modint t = *this;
        ++*this;
        return t;
    }

    modint operator-() const { return 0 - *this; }

    modint operator+() const { return *this; }

    modint pow(long long k = M - 2) const {
        modint f = *this, p = 1;
        while (k > 0) {
            if (k % 2 == 1) f *= p;
            p *= p, k /= 2;
        }
        return f;
    }

    int mod() const { return M; }

    friend modint operator+(modint l, const modint &r) { return l += r; }

    friend modint operator-(modint l, const modint &r) { return l -= r; }

    friend modint operator*(modint l, const modint &r) { return l *= r; }

    friend bool operator==(const modint &l, const modint &r) { return l.n == r.n; }

    friend bool operator!=(const modint &l, const modint &r) { return l.n != r.n; }

    friend ostream &operator<<(ostream &out, const modint &r) { return out << r.n; }

    int n;
};
modint c2 (modint x) {
    int64_t n = x.n;
    return (n * (n + 1)/2) % M;
}
const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<modint> h(N), w(N);
    vector<pair<modint, modint>> grid(N);
    set<int> s;
    for (int i = 0; i < N; i++) {
        cin >> h[i].n;
        s.insert(h[i].n);
    }
    vector<modint> pref = {0};
    for (int i = 0; i < N; i++) {
        cin >> w[i].n;
        pref.push_back(pref.back() + w[i]);
    }
    for (int i = 0; i < N; i++) {
        grid[i] = make_pair(w[i], h[i]);
    }
    modint ans = 0;
    for (modint x: s) {
        for (int i = 0; i < N; i++) {
            if (h[i] == x) {
                int l = i;
                while (l >= 1) {
                    if (h[l - 1].n >= x.n) {
                        l--;
                    } else {
                        break;
                    }
                }
                int r = i;
                while (r < N - 1) {
                    if (h[r + 1].n > x.n) {
                        r++;
                    } else {
                        break;
                    }
                }
                modint sum = (pref[i] - pref[l]) * (pref[r + 1] - pref[i + 1]);
                sum += (pref[r + 1] - pref[l] - w[i]) * w[i];
                ans += sum* c2(x);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        ans += c2(grid[i].first) * c2(grid[i].second);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

fancyfence.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("O3")
      | 
fancyfence.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("unroll-loops")
      | 
fancyfence.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("Ofast")
      |

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