제출 #1278989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278989		haithamcoder	Fancy Fence (CEOI20_fancyfence)	C++20	12 / 100	2 ms	584 KiB

fancyfence

#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;


#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 * (n - 1) / 2 % 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;
}

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