oj.uz

Submission #997770

# Submission time Handle Problem Language Result Execution time Memory
997770 2024-06-12T19:39:19 Z RaresFelix Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

#define int ll 
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;

const int MOD = 1e9 + 7;
const int inv2 = 5e8 + 4;

struct DSU {
    int re = 0;
    vi e, s;
    DSU(int n, const vi &S0) : e(n, -1), s(S0) {}

    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    void join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        re = (re - 1ll * s[u] * (s[u] + 1) % MOD * int(5e8 + 4) % MOD) % MOD;
        re = (re - 1ll * s[v] * (s[v] + 1) % MOD * int(5e8 + 4) % MOD) % MOD;
        s[u] += s[v];
        re = (re + 1ll * s[u] * (s[u] + 1) % MOD * int(5e8 + 4) % MOD) % MOD;

        re = (re + MOD) % MOD;
    }
};

signed main() {
    int n;
    cin >> n;
    vi W(n);
    vector<ii> H(n);
    for(int i = 0; i < n; ++i) {
        cin >> H[i].first;
        H[i].second = i;
    }
    for(int i = 0; i < n; ++i)
        cin >> W[i];
    DSU Sol(n, W);
    vi on(n, 0);
    sort(H.rbegin(), H.rend());
    ll s = 0, ant = 0;
    ll re = 0, hant = 0;
    H.push_back({0, 0});
    for(int i = 0; i < n; ++i) {
        int dr = i;
        do {
            int p = H[dr].second;
            s += 1ll * W[p] * (W[p] + 1) % MOD * inv2 % MOD;
            s %= MOD;
            on[p] = 1;
            if(p && on[p - 1]) Sol.join(p, p - 1);
            if(p + 1 < n && on[p + 1]) Sol.join(p, p + 1);
            ++dr;
        } while(dr < n && H[dr].first == H[dr - 1].first);
        int h = H[i].first;
        int fact = h * (h + 1) % MOD * inv2 % MOD;
        int uh = H[dr].first;
        int f2 = uh * (uh + 1) % MOD * inv2 % MOD;
        fact = fact - f2;
        fact = (fact % MOD + MOD) % MOD;

        ll cur = (s + Sol.re) % MOD;
        re = (re + cur * fact % MOD) % MOD;
        i = dr - 1;
    }
    cout << re << "\n";
    return 0;
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:53:15: warning: unused variable 'ant' [-Wunused-variable]
   53 |     ll s = 0, ant = 0;
      |               ^~~
fancyfence.cpp:54:16: warning: unused variable 'hant' [-Wunused-variable]
   54 |     ll re = 0, hant = 0;
      |                ^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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