oj.uz

Submission #1100057

# Submission time Handle Problem Language Result Execution time Memory
1100057 2024-10-12T15:16:41 Z ShaShi Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 2 ms 6492 KB 
#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))*(flag%MOD)%MOD; ans %= MOD; i = j;
    }

    cout << ans << endl;


    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -