oj.uz

Submission #447881

# Submission time Handle Problem Language Result Execution time Memory
447881 2021-07-27T23:51:52 Z flappybird Fancy Fence (CEOI20_fancyfence) C++14
12 / 100
 2 ms 332 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 101010
#define MOD 1000000007
#define ln '\n'
ll H[MAX], W[MAX];
ll sw[MAX];
ll ans = 0;
ll N;
struct segtree {
	ll N, s;
	vector<pll> tree;
	vector<ll> l, r;
	void init(ll x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s + 1;
			if (x - s + 1 > N) tree[x] = { INT32_MAX, l[x] };
			tree[x].second = l[x];
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
	}
	segtree(ll n) {
		N = n;
		s = 1LL << (ll)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
	}
	segtree() {}
	pll query(ll low, ll high, ll loc = 1) {
		if (l[loc] == low && r[loc] == high) return tree[loc];
		if (r[loc * 2] >= high) return query(low, high, loc * 2);
		if (l[loc * 2 + 1] <= low) return query(low, high, loc * 2 + 1);
		return min(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
	}
};
segtree seg;
void get(ll l, ll r) {
	if (l > r) return;
	ll res = seg.query(l, r).second;
	ll a = sw[r] - sw[l - 1];
	ll b = H[res];
	ll ls, rs;
	ls = sw[res] - sw[l - 1] - W[res];
	rs = sw[r] - sw[res];
	ll mem = a * (a + 1);
	mem -= ls * (ls + 1);
	mem -= rs * (rs + 1);
	mem %= MOD;
	mem *= b;
	mem %= MOD;
	mem *= (b + 1);
	mem %= MOD;
	while (mem % 4) mem += MOD;
	mem /= 4;
	ans += mem;
	ans %= MOD;
	get(l, res - 1);
	get(res + 1, r);
}
signed main() {
	ll N;
	cin >> N;
	ll i;
	seg = segtree(N);
	for (i = 1; i <= N; i++) cin >> H[i];
	for (i = 1; i <= N; i++) cin >> W[i], sw[i] = sw[i - 1] + W[i];
	for (i = 1; i <= N; i++) seg.tree[i + seg.s - 1] = { H[i], i };
	seg.init();
	get(1, N);
	cout << ans << ln;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 2 ms 332 KB Output isn't correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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