Submission #373467

#	Time	Username	Problem	Language	Result	Execution time	Memory
373467		jenkinsser	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	55 ms	4972 KiB

fancyfence

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/*
A not too simple solution:
Sort sections in decreasing order by height
Use DSU (why not?, it's a good practice) when merging intervals
Note that you don't need so many long long, i just wanted to be sure
Note that this is an O(NlogN) solution because of the sorting

Made for you by Mate Busa
*/

const long long mod = 1000000007;
long long N, ans;
long long h[100000];
long long w[100000];
vector<int> sections;
int parent[100000];
bool done[100000];

//calculate binom(x,2)
long long bin(long long x){
	x %= mod;
    return ((x*(x+1))/2)%mod;
}
//count fancy rectangles in a big rectangle of size x*y
long long rec(long long x, long long y){
    return (bin(x)*bin(y))%mod;
}

//DSU
int find_set(int x){
    if(parent[x]<0) return x;
    return (parent[x] = find_set(parent[x]));
}
void union_sets(int x, int y, long long high){
    x = find_set(x); y = find_set(y);
    long long h = (rec(w[x],high)+rec(w[y],high))%mod;
    h = (rec(w[x]+w[y],high)-h+mod)%mod; ans = (ans+h)%mod;
    if(parent[x]<parent[y]){
        parent[y] = x;
        w[x] = (w[x]+w[y])%mod;
    } else {
        if(parent[x]==parent[y]) parent[y]--;
        parent[x] = y;
        w[y] = (w[x]+w[y])%mod;
    }
}

bool smaller(int x, int y){
    return h[x]>h[y];
}

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

    cin >> N;

    for(int i=0; i<N; i++){
        cin >> h[i];
        sections.push_back(i); parent[i] = -1;
    }
    for(int i=0; i<N; i++) cin >> w[i];
    //sort sections by height
    sort(sections.begin(),sections.end(),smaller);

    for(int i=0; i<N; i++) ans = (ans+rec(w[i],h[i]))%mod;

    for(int i:sections){
        //merge intervals
        if(i!=0 && done[i-1]) union_sets(i-1,i,h[i]);
        if(i!=N-1 && done[i+1]) union_sets(i,i+1,h[i]);
        done[i] = true;
    }

    cout << ans << '\n';

    return 0;
}

• 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