제출 #1279201

#제출 시각아이디문제언어결과실행 시간메모리
1279201haithamcoderFancy Fence (CEOI20_fancyfence)C++20
25 / 100
39 ms8160 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll inv = (MOD + 1) / 2;


#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);

ll nc2(ll n) { return ((((n % MOD) * ((n - 1) % MOD)) % MOD)* inv) % MOD; }

void add(ll& a, ll b) {
    a = (a + b) % MOD;
}

void sub(ll& a, ll b) {
    a = (a - b + MOD) % MOD;
}

int main() {
    Algerian OI

    ll n;
    cin >> n;

    map<ll, vector<ll>> heights;
    vector<ll> h(n), w(n), p(n);
    ll r = 0;

    for (ll i = 0; i < n; i++) cin >> h[i];
    for (ll i = 0; i < n; i++) { cin >> w[i]; r += w[i], p[i] = r;}

    for (ll i = 0; i < n; i++) {
        heights[h[i]].push_back(i);
    }

    set<ll> points = {-1, n};
    // multiset<ll> len = {p[n - 1]};
    ll cur_segments = nc2(p[n - 1]);
    ll res = 0;

    for (ll i = 0; i < n; i++) res += (h[i] + nc2(h[i])) * w[i];

    // dbg(res);

    ll pre = 0;


    for (auto&  [u, v] : heights) {
        // dbg(u);
        ll delta = u - pre;
        add(res, cur_segments * (nc2(delta) + delta + delta * pre));
        pre = u;


        for (auto& pt : v) {
            auto it = points.lower_bound(pt);
            ll r = *it, l = *prev(it);
            
            ll length = p[r - 1] - (l >= 0 ? p[l] : 0);
            
            // len.erase(len.find(length));
            // dbg("here");

            sub(cur_segments, nc2(length));

            points.insert(pt);

            ll new_len[] = {(pt > 0 ? p[pt - 1] : 0) - (l >= 0 ? p[l] : 0), p[r - 1] - p[pt]};
            // len.insert(new_len[0]);
            // len.insert(new_len[1]);

            add(cur_segments, nc2(new_len[0]));
            add(cur_segments, nc2(new_len[1]));
        }
    }

    cout << res << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...