Submission #340195

#	Time	Username	Problem	Language	Result	Execution time	Memory
340195		blue	Fancy Fence (CEOI20_fancyfence)	C++11	100 / 100	373 ms	18884 KiB

fancyfence

#include <iostream>
#include <algorithm>
using namespace std;

/*
Sort all the rectangles by height.
Repeat:
    Look at the tallest rectangle with height H and width W.
    Let h be the larger height among its neighbors.
    Count all fancy rectangles whose top edge is in the range [h+1, H] = (W*(W+1)/2) * ((H-h)*(H-h+1)/2)
    Reduce the height of the tallest rectangle to h and merge it with the right neighbors

Reverse the above algorithm

Solution
Repeat:
    Look at the lowest rectangle with height H
    Find the rectangles to the left and right closest to this rectangle which have height strictly less than H.
        (Sparse table + Binary search)
    Let the total width bounded between (not inside either rectangle) these rectangles be W
    Add (Hchoose2 + Hchoose1) * (Wchoose2 + Wchoose1)
*/

long long N;
long long h[100002][18];
long long w[100001];
long long l2[100002];
long long rect[100001];

long long mod = 1e9 + 7;

long long hmin(long long l, long long r)
{
    return min(h[l][l2[r-l+1]], h[r - (1LL << l2[r-l+1]) + 1][l2[r-l+1]]);
}

int main()
{
    cin >> N;

    h[0][0] = h[N+1][0] = 0;
    for(long long i = 1; i <= N; i++)
    {
        cin >> h[i][0];
    }
    for(long long j = 1; j <= 17; j++)
    {
        for(long long i = 1; i + (1LL << j) - 1 <= N; i++)
        {
            h[i][j] = min(h[i][j-1], h[i + (1LL << (j-1))][j-1]);
        }
    }

    w[0] = 0;
    for(long long i = 1; i <= N; i++)
    {
        cin >> w[i];
        w[i] = (w[i] + w[i-1]) % mod;
    }

    l2[1] = 0;
    for(long long i = 2; i <= N; i++) l2[i] = l2[i/2] + 1;

    for(long long i = 0; i <= N; i++) rect[i] = i;
    sort(rect+1, rect+N+1,
        [] (long long a, long long b)
        {
            if(h[a][0] == h[b][0]) return a < b;
            return h[a][0] < h[b][0];
        }
    );
    //for(int i = 1; i <= N; i++) cout << rect[i] << ' ';
    //cout << '\n';

    long long res = 0;

    long long curr, L, R;
    long long x, y, m;
    for(long long i = 1; i <= N; i++)
    {
        curr = rect[i];
        if(h[curr][0] == h[rect[i-1]][0] && hmin(rect[i-1], curr) == h[curr][0]) continue;
    //    cout << curr << ' ' << h[curr][0] << ' ';

        x = 0;
        y = curr-1;
        while(x != y)
        {
            m = (x+y)/2 + 1;
            if(hmin(m, curr-1) >= h[curr][0]) y = m-1;
            else x = m;
        }
        L = x;
                                //Problem is, with nodes of equal heights
        x = curr+1;
        y = N+1;
        while(x != y)
        {
            m = (x+y)/2;
            if(hmin(curr+1, m) >= h[curr][0]) x = m+1;
            else y = m;
        }
        R = y;

        long long y1 = h[curr][0];
        //long long y2 = h[rect[i-1]][0];
        long long y2 = max(h[L][0], h[R][0]);
        long long x = w[R-1] - w[L];

        res = (res + (((x*(x+1))/2)%mod) * (( mod + (((y1*(y1+1))/2)%mod)  -  (((y2*(y2+1))/2)%mod)  ) % mod)) % mod;
        //cout << res << '\n';
    }
    cout << res << '\n';
}

• 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