oj.uz

Submission #534871

# Submission time Handle Problem Language Result Execution time Memory
534871 2022-03-09T05:21:43 Z ComPhyPark Fancy Fence (CEOI20_fancyfence) C++14
27 / 100
 356 ms 12996 KB 
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll M = 1000000007;
ll n;
ll h[101010], w[101010];
ll hst[303030], wst[303030];
void hinit(ll l, ll r, ll id) {
	if (l == r) {
		hst[id] = h[l];
		return;
	}
	ll m = (l + r) / 2;
	hinit(l, m, 2 * id);
	hinit(m + 1, r, 2 * id + 1);
	hst[id] = min(hst[2 * id], hst[2 * id + 1]);
}
void winit(ll l, ll r, ll id) {
	if (l == r) {
		wst[id] = w[l];
		return;
	}
	ll m = (l + r) / 2;
	winit(l, m, 2 * id);
	winit(m + 1, r, 2 * id + 1);
	wst[id] = wst[2 * id] + wst[2 * id + 1];
}
ll hqry(ll l, ll r, ll id, ll s, ll e) {
	if (l > e || s > r)return M;
	if (s <= l && r <= e)return hst[id];
	ll m = (l + r) / 2;
	return min(hqry(l, m, 2 * id, s, e), hqry(m + 1, r, 2 * id + 1, s, e));
}
ll wqry(ll l, ll r, ll id, ll s, ll e) {
	if (l > e || s > r)return 0;
	if (s <= l && r <= e)return wst[id];
	ll m = (l + r) / 2;
	return wqry(l, m, 2 * id, s, e) + wqry(m + 1, r, 2 * id + 1, s, e);
}
ll f(ll s, ll e, ll t) {
	if (s > e)return 0;
	ll mh = hqry(0, n - 1, 1, s, e);
	if (mh == t) {
		ll l = s, r = e, m;
		while (l < r) {
			m = (l + r) / 2;
			if (hqry(0, n - 1, 1, s, m) == t) {
				r = m;
			}
			else {
				l = m + 1;
			}
		}
		return (f(s, l - 1, t) + f(l + 1, e, t)) % M;
	}
	else {
		ll hn = (mh * (mh + 1) - t * (t + 1)) / 2;
		hn %= M;
		ll ws = wqry(0, n - 1, 1, s, e) % (2 * M), wn = ws * (ws + 1) / 2 % M;
		ll r = wn * hn % M;
		return r + f(s, e, mh);
	}
}
int main() {
	ll i;
	scanf("%lld", &n);
	for (i = 0; i < n; i++) {
		scanf("%lld", &h[i]);
	}
	for (i = 0; i < n; i++) {
		scanf("%lld", &w[i]);
	}
	hinit(0, n - 1, 1);
	winit(0, n - 1, 1);
	printf("%lld", f(0, n - 1, 0));
	return 0;
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
fancyfence.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%lld", &h[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
fancyfence.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%lld", &w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 272 KB Output is correct
2 Incorrect 1 ms 332 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 2 ms 320 KB Output is correct
2 Correct 31 ms 1732 KB Output is correct
3 Correct 156 ms 6856 KB Output is correct
4 Correct 338 ms 12796 KB Output is correct
5 Correct 345 ms 12820 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 26 ms 1688 KB Output is correct
4 Correct 161 ms 6992 KB Output is correct
5 Correct 332 ms 12996 KB Output is correct
6 Correct 356 ms 12896 KB Output is correct
7 Incorrect 2 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 276 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 1 ms 260 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Incorrect 2 ms 332 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 264 KB Output is correct
2 Correct 1 ms 276 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Correct 0 ms 284 KB Output is correct
9 Correct 1 ms 280 KB Output is correct
10 Incorrect 1 ms 292 KB Output isn't correct
11 Halted 0 ms 0 KB -