oj.uz

Submission #448779

# Submission time Handle Problem Language Result Execution time Memory
448779 2021-08-01T13:11:58 Z Aryan_Raina Fancy Fence (CEOI20_fancyfence) C++17
12 / 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 x : order) {
        int lw = 0, rw = 0;
        if (x-1 >= 0 && act[x-1]) {
            lw = ufds.wn[ufds.fin(x-1)];
            ufds.join(x, x-1);
        }
        if (x+1 < N && act[x+1]) {
            rw = ufds.wn[ufds.fin(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) + ((lw * rw % MOD) * a % MOD) % MOD;
        ans %= MOD;

        act[x] = true;
    }
 
    ans = (ans + MOD) % MOD;
    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 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
12.0 / 12.0

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

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 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct