Submission #466140

#	Time	Username	Problem	Language	Result	Execution time	Memory
466140		training4usaco	Fancy Fence (CEOI20_fancyfence)	C++11	12 / 100	2 ms	460 KiB

fancyfence

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

#define MOD 1000000007

int n;
vector<int> sizes(10002);
vector<int> parent(10002);
vector<int> width(10002);
vector<int> height(10002);
vector<int> answer(10002);

int nc2(int x) {
    return (x * (x - 1)/2) % MOD;
}

int numRect(int w, int h) {
    return (nc2(w + 1) * nc2(h + 1)) % MOD;
}

void init()
{
	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
		sizes[i] = 1;
	}
}

int getRoot(int x)
{
	if (x == parent[x])
	{
		return x;
	}
	return parent[x] = getRoot(parent[x]);
}

bool merge(int x, int y, int h) {
    // cout << "x, y, h: " << x << " " << y << " " << h << endl;
    x = getRoot(x);
    y = getRoot(y);

    if(x == y) {
        return false;
    }

	if (sizes[x] > sizes[y])
	{
		swap(x, y);
	}

    answer[x] += (numRect(width[x], height[x]) - numRect(width[x], h));
    answer[x] %= MOD;
    answer[y] += (numRect(width[y], height[y]) - numRect(width[y], h));
    answer[y] %= MOD;

    sizes[x] += sizes[y];
	parent[y] = x;

    width[x] += width[y];
    width[x] %= MOD;

    answer[x] += answer[y];
    answer[x] %= MOD;
	
    height[x] = h;

    // cout << "answer[" << x << "]: " << answer[x] << endl;

    return true;
}

bool comp(int a, int b) {
    if(height[a] == height[b]) {
        return width[a] < width[b];
    }
    return height[a] > height[b];
}

int main() {
    cin >> n;
    init();

    for(int i = 1; i <= n; ++i) {
        cin >> height[i];
    }
    for(int j = 1; j <= n; ++j) {
        cin >> width[j];
    }

    vector<int> idx(n);
    for(int i = 0; i < n; ++i) {
        idx[i] = i + 1;
    }

    sort(idx.begin(), idx.end(), comp);

    // for(int i = 0; i < idx.size(); ++i) {
    //     cout << idx[i] << endl;
    // }

    for(int i : idx) {
        // cout << "i, root of i: " << i << " " << getRoot(i) << endl;
        if(i != 1 && height[getRoot(i - 1)] >= height[getRoot(i)]) {
            merge(i, i - 1, height[i]);
        }
        if(i != n && height[getRoot(i + 1)] >= height[getRoot(i)]) {
            merge(i, i + 1, height[i]);
        }
    }

    int root = getRoot(1);

    answer[root] += numRect(width[root], height[root]);
    answer[root] %= MOD;

    cout << answer[root] << endl;

    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27