Submission #533292

#	Time	Username	Problem	Language	Result	Execution time	Memory
533292		ddy888	Fancy Fence (CEOI20_fancyfence)	C++17	15 / 100	29 ms	2008 KiB

fancyfence

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

const int MOD = 1e9 + 7;
int N, H[100010], W[100010], par[100010], sz[100010], ans;
vector<pi> blocks, proc;

int root(int x) { return (par[x]==x)? x:par[x]=root(par[x]); }
bool same(int a, int b) { return root(a) == root(b); }
void merge(int a, int b) {
    if (same(a, b)) return;
    sz[root(b)] += sz[root(a)];
    par[root(a)] = root(b);
}
int getsize(int x) {return sz[root(x)];}

int binom(int x) {
    x %= MOD;
    return (x * (x + 1) / 2) % MOD;
}

int f(int x, int y) {
    return (binom(x) * binom(y)) % MOD;
}

signed main() {
    fast;
    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> H[i];
    for (int i = 1; i <= N; ++i) cin >> W[i];
    for (int i = 1; i <= N; ++i) {
        if (H[i] == H[i - 1]) proc.back().si += W[i];
        else proc.pb({H[i], W[i]});
    }
    int lim = proc.size();
    for (int i = 0; i < lim; ++i) blocks.pb({proc[i].fi, i});
    for (int i = 0; i < lim; ++i) par[i] = i, sz[i] = proc[i].si;
    sort(blocks.begin(), blocks.end(), [](pi a, pi b) {
        return a.fi > b.fi;
    });
    for (auto i: blocks) {
        if (i.si > 0 && proc[i.si].fi <= proc[i.si - 1].fi) {
            ans = f(getsize(i.si - 1), proc[i.si].fi) + MOD; ans %= MOD;
            merge(i.si, i.si - 1);
        } 
        if (i.si < lim - 1 && proc[i.si].fi <= proc[i.si + 1].fi) {
            ans = f(getsize(i.si + 1), proc[i.si].fi) + MOD; ans %= MOD;
            merge(i.si, i.si + 1);
        }
        ans += f(getsize(i.si), proc[i.si].fi);
        ans %= MOD;
    }
    cout << ans;
    return 0;
}

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