Submission #1011607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011607		Essa2006	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	43 ms	5628 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)

int n, sum, inv2 = (mod + 1) / 2;
vector<int> P, W;

void pre() {
    P.resize(n), W.resize(n);
}
int add(int a, int b) {
    if (b < mod) {
        b += mod;
        b %= mod;
    }
    return ((a + b) % mod + mod) % mod;
}

int mul(int a, int b) {
    a %= mod, b %= mod;
    return (ll) a * b % mod;
}

int nm(int k) {
    return mul(k, mul(add(k, 1), inv2));
}

int sm (int h2, int h1) {
    return add(nm(h2), -nm(h1 - 1));
}

int find(int ind) {
    if (ind == P[ind]) {
        return ind;
    }
    return P[ind] = find(P[ind]);
}

void merge(int a, int b) {
    int ga = find(a), gb = find(b);

    if (ga == gb) {
        return;
    }
    if(rand() & 1) {
        swap(ga, gb);
    }

    sum = add(sum, -nm(W[gb]));
    sum = add(sum, -nm(W[ga]));
    P[ga] = gb;
    W[gb] = add(W[gb], W[ga]);
    sum = add(sum, nm(W[gb]));
}



int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    pre();

    vector<array<int, 3>> A(n), C(n);
    for (int j = 0; j < 2; j++) {
        for (int i = 0; i < n; i++) {
            cin >> A[i][j];
            C[i][j] = A[i][j];
            A[i][2] = i;
        }
    }

    for (int i = 0; i < n; i++) {
        P[i] = i, W[i] = C[i][1];
    }

    sort(all(A)), reverse(all(A));
    int ans = 0, last;
    for (int i = 0; i < n; i++) {
        if (i && A[i][0] != A[i - 1][0]) {
            ans = add(ans, mul(sum, sm(last, A[i][0] + 1)));
        }
        sum = add(sum, nm(C[A[i][2]][1]));
        if (A[i][2] && C[A[i][2] - 1][0] >= A[i][0]) {
            merge(A[i][2], A[i][2] - 1);
        }
        if (A[i][2] != n - 1 && C[A[i][2] + 1][0] >= A[i][0]) {
            merge(A[i][2], A[i][2] + 1);
        }

        last = A[i][0];
    }
    ans = add(ans, mul(sum, sm(last, 1)));
    cout << ans << endl;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:98:14: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     ans = add(ans, mul(sum, sm(last, 1)));
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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