oj.uz

Submission #448757

# Submission time Handle Problem Language Result Execution time Memory
448757 2021-08-01T12:24:29 Z Aryan_Raina Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
#define ld long double
#define ar array
#define all(a) a.begin(), a.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e12;
const int MOD = 1e9+7;
const int inv2 = 5e8+4;
  
struct UFDS {
    vector<int> p, wn;
    UFDS(int n) : p(n,-1), wn(n, 0) {}
    int fin(int v) { return p[v] < 0 ? v : p[v] = fin(p[v]); }
    bool join(int a, int b) {
        a = fin(a), b = fin(b);
        if (a == b) return false;
        if (-p[a] < -p[b]) swap(a, b);
        p[a] += p[b]; p[b] = a; wn[a] += wn[b];
        return true;
    }
};

void solve() {
    int N; cin >> N;
    vector<int> h(N), w(N);
    UFDS ufds(N);
    for (int &i : h) cin >> i;
    for (int &i : w) cin >> i;
    for (int i = 0; i < N; i++) ufds.wn[i] = w[i];

    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) { return h[a] > h[b]; });

    int ans = 0;
    vector<bool> act(N, false);
    for (int i = 0; i < N; i++) {
        int x = order[i];

        if (x-1 >= 0 && act[x-1]) ufds.join(x, x-1);
        if (x+1 < N && act[x+1]) ufds.join(x, x+1);

        int a = (h[x] * (h[x] + 1) % MOD) * inv2 % MOD;
        int b = (w[x] * ufds.wn[ufds.fin(x)]) % MOD - ((w[x] - 1) * w[x] % MOD * inv2 % MOD);
        b = (b % MOD + MOD) % MOD;

        ans += a * b % MOD;
        ans %= MOD;

        act[x] = true;
    }

    cout << ans << '\n';
} 
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 

    int t = 1; //cin >> t;
    while (t--) solve();   
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct