Submission #1100067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100067		ShaShi	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	29 ms	10704 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, inv2;
pair<int, pii> arr[MAXN];
int par[MAXN], sz[MAXN];
bool seen[MAXN];



int POW(int x, int y) {
    if (y == 0) return 1;
    if (y&1) return x*POW(x*x%MOD, y/2)%MOD;
    return POW(x*x%MOD, y/2);
}



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


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

    if (u == v) return;

    flag = (flag-(f(sz[u])+f(sz[v]))+10*MOD)%MOD;

    par[u] = v; sz[v] = (sz[v]+sz[u])%MOD;

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


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 = (flag+f(sz[arr[ind].S.S]))%MOD;
    
    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("inp2.txt", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    inv2 = POW(2, MOD-2);

    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;

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

    cout << ans << endl;


    return 0;
}

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