oj.uz

Submission #527332

# Submission time Handle Problem Language Result Execution time Memory
527332 2022-02-17T08:20:29 Z x0r Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 58 ms 7108 KB 
#pragma GCC optimize ("O2")
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define fi first 
#define se second
#define pll pair < ll, ll >
#define pii pair < int, int >
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const string NAME = "fence2";
const string NAME2 = "TEST";
const ll ESP = 1e-9;
const ll INF = 1e18;
const ll nmax = 2e5;
const ll MOD = 1e9 + 7;
const ll base = 2309;

void fre() {
	string finp = NAME + ".inp";
	string fout = NAME + ".out";
	freopen(finp.c_str(), "r", stdin);
	freopen(fout.c_str(), "w", stdout);
}

ll n, h[1000004], w[1000003], sw[1000003], l[1000003], r[1000003];

ll mu(ll a, ll b) {
	if (b == 0) return 1;
	ll x = mu(a, b / 2);
	x = (x * x) % MOD;
	if (b % 2 == 1) x = (x * a) % MOD;
	return x;
}

ll calc(ll x) {
	x = (x + MOD) % MOD;
	return (((x * (x + 1)) % MOD) * mu(2, MOD - 2)) % MOD;
}

ll count(ll h, ll w) {
	return (calc(h) * calc(w)) % MOD;
}

void sol() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		sw[i] = sw[i - 1] + w[i];
		sw[i] %= MOD;
	}
	h[0] = h[n + 1] = 0;
 	stack < ll > st;
	for (int i = 1; i <= n; i++) {
		while (st.size() && h[st.top()] > h[i]) st.pop();
		if (!st.size()) l[i] = 1;
		else l[i] = st.top() + 1;
		st.push(i);
	}
	stack < ll > st2;
	for (int i = n; i >= 1; i--) {
		while (st2.size() && h[st2.top()] >= h[i]) st2.pop();
		if (!st2.size()) r[i] = n;
		else r[i] = st2.top() - 1;
		st2.push(i);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ll tam = max(h[l[i] - 1], h[r[i] + 1]);
		ans = (ans + count(h[i], sw[r[i]] - sw[l[i] - 1]) - count(tam, sw[r[i]] - sw[l[i] - 1]) + MOD) % MOD;
	}
	cout << ans;
}

int main() {
	fast;
	//fre();
	int t = 1;
	//cin >> t;
	while (t --) sol();
}

Compilation message

fancyfence.cpp: In function 'void fre()':
fancyfence.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen(finp.c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:26:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  freopen(fout.c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 22 ms 3012 KB Output is correct
4 Correct 44 ms 5956 KB Output is correct
5 Correct 51 ms 5712 KB Output is correct
6 Correct 38 ms 5440 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 5 ms 716 KB Output is correct
3 Correct 22 ms 2728 KB Output is correct
4 Correct 49 ms 5060 KB Output is correct
5 Correct 57 ms 5072 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 5 ms 972 KB Output is correct
4 Correct 22 ms 3648 KB Output is correct
5 Correct 47 ms 6912 KB Output is correct
6 Correct 58 ms 7028 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 6 ms 1020 KB Output is correct
9 Correct 23 ms 3780 KB Output is correct
10 Correct 47 ms 6872 KB Output is correct
11 Correct 44 ms 6984 KB Output is correct
12 Correct 0 ms 332 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 20 ms 3016 KB Output is correct
12 Correct 39 ms 6092 KB Output is correct
13 Correct 41 ms 5660 KB Output is correct
14 Correct 38 ms 5440 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 7 ms 956 KB Output is correct
17 Correct 24 ms 3720 KB Output is correct
18 Correct 48 ms 6904 KB Output is correct
19 Correct 48 ms 7108 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 5 ms 964 KB Output is correct
22 Correct 24 ms 3656 KB Output is correct
23 Correct 51 ms 6904 KB Output is correct
24 Correct 53 ms 6980 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 328 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 452 KB Output is correct
30 Correct 6 ms 888 KB Output is correct
31 Correct 5 ms 840 KB Output is correct
32 Correct 28 ms 3268 KB Output is correct
33 Correct 22 ms 3196 KB Output is correct
34 Correct 46 ms 6072 KB Output is correct
35 Correct 45 ms 6012 KB Output is correct
36 Correct 47 ms 6188 KB Output is correct
37 Correct 46 ms 6140 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 44 ms 6084 KB Output is correct
40 Correct 44 ms 6204 KB Output is correct
41 Correct 44 ms 6284 KB Output is correct
42 Correct 43 ms 6600 KB Output is correct