oj.uz

Submission #970633

# Submission time Handle Problem Language Result Execution time Memory
970633 2024-04-27T01:38:24 Z biximo Fancy Fence (CEOI20_fancyfence) C++17
15 / 100
 22 ms 8788 KB 
#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef long long ll;
ll wth[N], hgt[N], ans;
int p[N];
const int MOD = 1e9+7, DIV = (1e9+8)/2;
int get(int a) {
	if(p[a] != a) p[a]=get(p[a]);
	return p[a];
}
void join(int a, int b) {
	a = get(a); b = get(b);
	if(a == b) return;
	if(hgt[a] < hgt[b]) swap(a,b);
	ans += (1+wth[a])*(wth[a])%MOD*DIV%MOD*(hgt[a]+hgt[b]+1)%MOD*(hgt[a]-hgt[b])%MOD*DIV%MOD;
	ans %= MOD;
	wth[a] += wth[b];
	wth[a] %= MOD;
	hgt[a] = hgt[b];
	p[b] = a;
}
int H[N], W[N], order[N], n;
bool comp(int a, int b) {
	if(H[a] == H[b]) {
		return a > b;
	}
	return H[a] < H[b];
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) {
    	cin >> H[i];
    }
    for(int i = 1; i <= n; i ++) {
    	cin >> W[i];
    	wth[i] = W[i];
    	hgt[i] = H[i];
    	order[i] = i;
    	p[i] = i;
    }
    sort(order+1, order+1+n);
    for(int j = 1; j <= n; j ++) {
    	int i = order[j];
    	if(i-1 && !comp(i-1, i)) {
    		join(i,i-1);
    	}
    	if(i+1<=n && !comp(i+1, i)) {
    		join(i,i+1);
    	}
    }
    int i = get(1);
    ans += wth[i]*hgt[i]%MOD*(wth[i]+1)%MOD*(hgt[i]+1)%MOD*DIV%MOD*DIV%MOD;
    ans %= MOD;
    if(ans < 0) ans += MOD;
    cout << ans;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 13 ms 6472 KB Output is correct
4 Correct 20 ms 8536 KB Output is correct
5 Correct 22 ms 8788 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4600 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 10 ms 6468 KB Output is correct
5 Correct 20 ms 8480 KB Output is correct
6 Correct 20 ms 8540 KB Output is correct
7 Incorrect 1 ms 4576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

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