oj.uz

Submission #667541

# Submission time Handle Problem Language Result Execution time Memory
667541 2022-12-01T17:07:26 Z dozer Fancy Fence (CEOI20_fancyfence) C++14
0 / 100
 2 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define endl "\n"
#define sp " "
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define L(node) node * 2
#define R(node) node * 2 + 1
#define int long long

const int INF = 1e9 + 7;
const int modulo = 1e9 + 7;


int h[N], w[N], pre[N];
pii tree[N * 4];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = {h[l], l};
		return;
	}
	int mid = (l + r) / 2;
	build(L(node), l, mid);
	build(R(node), mid + 1, r);
	tree[node] = min(tree[L(node)], tree[R(node)]);
}


pii find(int node, int l, int r, int sl, int sr)
{
	if (l > r || l > sr || r < sl) return {INF, INF};
	if (l >= sl && r <= sr) return tree[node];
	int mid = (l + r) / 2;
	return min(find(L(node), l, mid, sl, sr), find(R(node), mid + 1, r, sl, sr));
}

int ans, n;

int add(int a, int b)
{
	if (a + b < modulo) return a + b;
	return a + b - modulo;
}

int mul(int a, int b)
{
	return (a * b) % modulo;
}


int subs(int a, int b)
{
	if (a < b) return a - b + modulo;
	return a - b;
}

int fe(int a, int b)
{
	if (b == 0) return 1;
	if (b % 2) return mul(a, fe(a, b - 1));
	int tmp = fe(a, b / 2);
	return mul(tmp, tmp);
}


void f(int l, int r, int prev)
{
	pii tmp = find(1, 1, n, l, r);
	//cout<<l<<sp<<r<<sp<<tmp.st<<sp<<tmp.nd<<endl;
	int maks = tmp.st;
	int ind = tmp.nd;
	int sum = subs(pre[r], pre[l - 1]);
	int x = mul(sum, sum + 1);
	//cout<<x<<sp;
	x = mul(x, fe(2, modulo - 2));
	//cout<<x<<sp;
	x = mul(x, maks);
	//cout<<x<<endl;
	ans = add(ans, x);
	if (ind > l) f(l, ind - 1, maks);
	if (ind < r) f(ind + 1, r, maks);
}

int32_t main()
{
	//fileio();
	fastio();

	cin>>n;
	for (int i = 1; i <= n; i++)
		cin>>h[i];
	for (int j = 1; j <= n; j++)
	{
		cin>>w[j];
		pre[j] = add(pre[j - 1], w[j]);
	}
	build(1, 1, n);
	f(1, n, 0);
	cout<<ans<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
0.0 / 0.0

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