Submission #533289

#	Time	Username	Problem	Language	Result	Execution time	Memory
533289		ddy888	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	1 ms	340 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;

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) {
    sz[root(b)] += sz[root(a)];
    par[root(a)] = root(b);
}
int getsize(int x) {return sz[root(x)];}

int f(int ww, int hh) {
    return ((hh * (hh + 1) % MOD * ww * (ww + 1) % MOD) % MOD / 4) % 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) blocks.pb({H[i], i});
    sort(blocks.begin(), blocks.end(), [](pi a, pi b) {
        return a.fi > b.fi;
    });
    for (int i = 1; i <= N; ++i) par[i] = i, sz[i] = W[i];
    for (auto i: blocks) {
        if (i.si > 1 && H[i.si] <= H[i.si - 1]) { // left 
            ans -= f(getsize(i.si - 1), H[i.si]);
            merge(i.si, i.si - 1);
        } 
        if (i.si < N && H[i.si] <= H[i.si + 1]) { // right
            ans -= f(getsize(i.si + 1), H[i.si]);
            merge(i.si, i.si + 1);
        }
        ans += f(getsize(i.si), H[i.si]);
        ans %= MOD;
    }
    cout << ans;
    return 0;
}

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