Submission #1100059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100059		ShaShi	Fancy Fence (CEOI20_fancyfence)	C++17	12 / 100	1 ms	6492 KiB

fancyfence

#include <bits/stdc++.h>
 
#define int long long 
 
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
 
const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e9 + 7;
 
 
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, N, X, Y;
pair<int, pii> arr[MAXN];
int par[MAXN], sz[MAXN];
bool seen[MAXN];


inline int get_par(int v) { return (par[v] == v? v : par[v] = get_par(par[v])); }
inline int f(int n) { return n*(n+1)/2; }


inline void merge(int u, int v) {
    u = get_par(u); v = get_par(v);

    if (u == v) return;

    flag -= f(sz[u])+f(sz[v]);

    par[u] = v; sz[v] += sz[u];

    flag += f(sz[v]);
}


void add(int ind) {
    par[arr[ind].S.S] = arr[ind].S.S; sz[arr[ind].S.S] = arr[ind].S.F; 
    seen[arr[ind].S.S] = 1; flag += f(sz[arr[ind].S.S]);
    
    if (seen[arr[ind].S.S-1]) merge(arr[ind].S.S, arr[ind].S.S-1);
    if (seen[arr[ind].S.S+1]) merge(arr[ind].S.S, arr[ind].S.S+1);
}



int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n;

    for (int i=1; i<=n; i++) cin >> arr[i].F;
    for (int i=1; i<=n; i++) cin >> arr[i].S.F;
    for (int i=1; i<=n; i++) arr[i].S.S = i;

    sort(arr+1, arr+n+1, greater<pair<int, pii>>());

    ans = 0;

    for (int i=1; i<=n;) {
        int j = i;

        while (j <= n && arr[j].F == arr[i].F) add(j++);

        // cout << "! " << i << " " << j << " " << flag << " " << arr[i].F << endl;

        ans += ((f(arr[i].F)-f(arr[j].F))%MOD)*(flag%MOD)%MOD; ans %= MOD; i = j;
    }

    cout << ans << endl;


    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