Submission #674797

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
674797	2022-12-26T08:33:11 Z	faribourz	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	70 ms	5832 KB

fancyfence

// Only GOD
// believe in yourself
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define bit(x, y) ((x >> y)&1)
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define int ll 
const int N = 1e5+10;
const int INF = 1e9+10;
const int MOD = 1e9+7;
int mul(int a, int b){
	a %= MOD;
	b %= MOD;
	return (a*b)%MOD;
}
int add(int a, int b){
	return (a+b+MOD)%MOD;
}
int dp[N], h[N], w[N], ps[N], psw[N];
int inv;
int f(int n){
	return mul(mul(n, n+1)%MOD, inv)%MOD;
}
int pw(int a, int b){
	int res = 1;
	while(b){
		if(b & 1)
			res = mul(a, res);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
int node[N << 1];
void upd(int x, int p){
	p += N;
	node[p] = x;
	p >>= 1;
	for(; p; p >>= 1)
		node[p] = min(node[p*2], node[p*2+1]); 
}
int get(int l, int r){
	int mn = INF;
	l += N, r += N;
	while(l < r){
		if(l&1)
			mn = min(node[l++], mn);
		if(r & 1)
			mn = min(node[--r], mn);
		l >>= 1;
		r >>= 1;
	}
	return mn;
}
int get2(int l, int r, int val){
	if(get(l, r) >= val)
		return -1;
	while(r - l > 1){
		int mid = (l+r)>>1;
		if(get(mid, r) < val)
			l = mid;
		else
			r = mid;
	}
	return l;
}
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(int i = 0; i < 2*N; i++)
		node[i] = INF;
	int n;
	cin >> n;
	inv = pw(2, MOD-2);
	for(int i = 1; i <= n; i++){
		cin >> h[i];
		upd(h[i], i);
	}
	for(int i = 1; i <= n;i++){
		cin >> w[i];
		psw[i] = psw[i-1]+w[i];
	}
	int ans=0;
	for(int i = 1; i <= n; i++){
		dp[i] = mul(w[i], f(h[i]));
		dp[i] = add(dp[i], mul(f(w[i]-1), f(h[i])));
		if(h[i] < h[i-1]){
			int j = get2(1, i, h[i]);
			if(j==-1){
				ps[i-1] = mul(psw[i-1], f(h[i]));
			}
			else{
				ps[i-1] = add(ps[j], mul(psw[i-1] - psw[j], f(h[i])));
			}
		}
		ps[i] = add(mul(w[i], f(h[i])),ps[i-1]);
		int res =0;
		res = ps[i-1];
		dp[i] = add(dp[i], mul(res, w[i]));
		ans = add(ans, dp[i]);
	}
	KILL(ans);
}

Subtask #1

0.0 / 0.0

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

Subtask #2

12.0 / 12.0

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

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	12 ms	3824 KB	Output is correct
4	Correct	24 ms	5708 KB	Output is correct
5	Correct	24 ms	5772 KB	Output is correct
6	Correct	28 ms	5728 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	3 ms	2260 KB	Output is correct
3	Correct	15 ms	3752 KB	Output is correct
4	Correct	27 ms	5740 KB	Output is correct
5	Correct	31 ms	5704 KB	Output is correct
6	Correct	1 ms	1876 KB	Output is correct

Subtask #5

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	3 ms	2260 KB	Output is correct
4	Correct	15 ms	3768 KB	Output is correct
5	Correct	30 ms	5728 KB	Output is correct
6	Correct	29 ms	5700 KB	Output is correct
7	Correct	1 ms	1876 KB	Output is correct
8	Correct	4 ms	2260 KB	Output is correct
9	Correct	14 ms	3824 KB	Output is correct
10	Correct	26 ms	5716 KB	Output is correct
11	Correct	27 ms	5704 KB	Output is correct
12	Correct	1 ms	1876 KB	Output is correct

Subtask #6

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	1 ms	1876 KB	Output is correct
5	Correct	1 ms	1876 KB	Output is correct
6	Correct	1 ms	1876 KB	Output is correct
7	Correct	1 ms	1896 KB	Output is correct
8	Correct	1 ms	1940 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	1 ms	1876 KB	Output is correct
11	Correct	1 ms	1876 KB	Output is correct
12	Correct	1 ms	1876 KB	Output is correct
13	Correct	1 ms	1876 KB	Output is correct
14	Correct	1 ms	1876 KB	Output is correct
15	Correct	2 ms	1876 KB	Output is correct
16	Correct	1 ms	1876 KB	Output is correct

Subtask #7

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	2 ms	1876 KB	Output is correct
5	Correct	1 ms	1876 KB	Output is correct
6	Correct	1 ms	1876 KB	Output is correct
7	Correct	1 ms	1876 KB	Output is correct
8	Correct	1 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	1 ms	1876 KB	Output is correct
11	Correct	13 ms	3856 KB	Output is correct
12	Correct	24 ms	5712 KB	Output is correct
13	Correct	25 ms	5716 KB	Output is correct
14	Correct	25 ms	5748 KB	Output is correct
15	Correct	1 ms	1876 KB	Output is correct
16	Correct	4 ms	2260 KB	Output is correct
17	Correct	14 ms	3796 KB	Output is correct
18	Correct	26 ms	5748 KB	Output is correct
19	Correct	31 ms	5680 KB	Output is correct
20	Correct	1 ms	1876 KB	Output is correct
21	Correct	3 ms	2260 KB	Output is correct
22	Correct	14 ms	3796 KB	Output is correct
23	Correct	29 ms	5716 KB	Output is correct
24	Correct	27 ms	5672 KB	Output is correct
25	Correct	1 ms	1876 KB	Output is correct
26	Correct	2 ms	1876 KB	Output is correct
27	Correct	1 ms	1876 KB	Output is correct
28	Correct	1 ms	1884 KB	Output is correct
29	Correct	2 ms	1876 KB	Output is correct
30	Correct	6 ms	2288 KB	Output is correct
31	Correct	6 ms	2260 KB	Output is correct
32	Correct	31 ms	3808 KB	Output is correct
33	Correct	33 ms	3812 KB	Output is correct
34	Correct	68 ms	5832 KB	Output is correct
35	Correct	67 ms	5676 KB	Output is correct
36	Correct	70 ms	5664 KB	Output is correct
37	Correct	69 ms	5720 KB	Output is correct
38	Correct	1 ms	1876 KB	Output is correct
39	Correct	68 ms	5720 KB	Output is correct
40	Correct	69 ms	5696 KB	Output is correct
41	Correct	63 ms	5708 KB	Output is correct
42	Correct	30 ms	5716 KB	Output is correct