oj.uz

Submission #577521

# Submission time Handle Problem Language Result Execution time Memory
577521 2022-06-15T03:42:27 Z amunduzbaev Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 28 ms 5152 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 inv = 5e8 + 4;
	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 T = (pref[r[i] - 1] - pref[l[i]]) % mod;
		int tot = (T * 1ll * (T + 1) % mod - L * 1ll * (L + 1) % mod - R * 1ll * (R + 1) % mod + mod + mod) % mod;
		tot = tot * 1ll * inv % mod;
		//~ T = (w[i] * 1ll * (w[i] + 1) / 2 % mod + L * 1ll * R % mod + w[i] * 1ll * (L + R) % mod) % mod;
		//~ cout<<T<<" "<<tot<<"\n";
		T = h[i] * 1ll * (h[i] + 1) / 2 % mod;
		res = (res + tot * 1ll * T) % mod;
	}
	
	cout<<res<<"\n";
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 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 0 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 872 KB Output is correct
3 Correct 11 ms 2772 KB Output is correct
4 Correct 21 ms 5124 KB Output is correct
5 Correct 28 ms 5136 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 11 ms 2772 KB Output is correct
5 Correct 22 ms 5044 KB Output is correct
6 Correct 27 ms 5044 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 13 ms 2772 KB Output is correct
10 Correct 24 ms 5152 KB Output is correct
11 Correct 23 ms 5068 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 0 ms 340 KB Output is correct
2 Incorrect 1 ms 288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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