oj.uz

Submission #577514

# Submission time Handle Problem Language Result Execution time Memory
577514 2022-06-15T03:27:21 Z amunduzbaev Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 28 ms 7176 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int h[N], w[N], pref[N];
int l[N], r[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
		pref[i] = pref[i-1] + w[i];
	}
	
	vector<int> ss;
	for(int i=1;i<=n;i++){
		while(!ss.empty() && h[ss.back()] > h[i]){
			ss.pop_back();
		}
		
		if(!ss.empty()) l[i] = ss.back();
		else l[i] = 0;
		ss.push_back(i);
	}
	
	ss.clear();
	for(int i=n;i>0;i--){
		while(!ss.empty() && h[ss.back()] >= h[i]){
			ss.pop_back();
		}
		
		if(!ss.empty()) r[i] = ss.back();
		else r[i] = n + 1;
	}
	
	int res = 0;
	for(int i=1;i<=n;i++){
		int L = (pref[i-1] - pref[l[i]]) % mod, R = (pref[r[i]-1] - pref[i]) % mod;
		int tot = (w[i] * 1ll * (w[i] + 1) / 2 % mod + L * 1ll * R % mod + w[i] * 1ll * (L + R) % mod) % mod;
		res = (res + tot * 1ll * (h[i] * 1ll * (h[i] + 1) / 2 % mod)) % mod;
	}
	
	cout<<res<<"\n";
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 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 340 KB Output is correct
2 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 3 ms 1104 KB Output is correct
3 Correct 14 ms 3708 KB Output is correct
4 Correct 24 ms 7028 KB Output is correct
5 Correct 28 ms 7076 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 13 ms 3768 KB Output is correct
5 Correct 23 ms 7012 KB Output is correct
6 Correct 25 ms 7176 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 3 ms 1076 KB Output is correct
9 Correct 13 ms 3772 KB Output is correct
10 Correct 24 ms 6960 KB Output is correct
11 Correct 23 ms 7036 KB Output is correct
12 Correct 0 ms 340 KB Output is correct

Subtask #6
0 / 18.0

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