oj.uz

Submission #577527

# Submission time Handle Problem Language Result Execution time Memory
577527 2022-06-15T03:51:08 Z amunduzbaev Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 6 ms 388 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 = h[i] * 1ll * (h[i] + 1) / 2 % mod;
		//~ res = (res + tot * 1ll * T) % mod;
	//~ }
	
	for(int i=1;i<=n;i++){
		int mn = h[i];
		for(int j=i+1;j<=n;j++){
			mn = min(mn, h[j]);
			int t = mn * 1ll * (mn + 1) / 2 % mod;
			res = (res + t * 1ll * w[i] % mod * w[j]) % mod;
		}
		int W = w[i] * 1ll * (w[i] + 1) / 2 % mod;
		int H = h[i] * 1ll * (h[i] + 1) / 2 % mod;
		res = (res + W * 1ll * H % mod);
	}
	
	cout<<res<<"\n";
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:45:6: warning: unused variable 'inv' [-Wunused-variable]
   45 |  int inv = 5e8 + 4;
      |      ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct

Subtask #2
12.0 / 12.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 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 4 ms 340 KB Output isn't correct
9 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 Correct 6 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Incorrect 4 ms 388 KB Output isn't correct
11 Halted 0 ms 0 KB -