oj.uz

Submission #466358

# Submission time Handle Problem Language Result Execution time Memory
466358 2021-08-18T23:19:39 Z training4usaco Fancy Fence (CEOI20_fancyfence) C++11
12 / 100
 2 ms 460 KB 
#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];
    sizes[y] = sizes[x];
	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[i]) {
            merge(i, i - 1, height[i]);
        }
        if(i != n && height[getRoot(i + 1)] >= height[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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 2 ms 460 KB Output isn't correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 2 ms 460 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 460 KB Output is correct
2 Incorrect 2 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 2 ms 460 KB Output isn't correct